56.          Összefüggő gráfokban e≥n–1. Ha e=n–1, azaz a gráf fa, akkor nyilván egyetlen ilyen részgráf van, hiszen minden erdőben van elsőfokú pont, kivéve az üres gráfot. Ha e=n és a gráf összefüggő, akkor egy köre van (ld. a 23. feladatot). Ha ennek a körnek bármely élét elhagyjuk, akkor már egy legfeljebb n–1 élű gráfot kapunk, amelyről azt is tudjuk, hogy körmentes. Így minden komponense fa. Ha valamelyik komponense nem üres, azaz tartalmaz élt, akkor a 39. feladat szerint van benne (legalább két) elsőfokú pont, tehát az ilyen részgráf nem megfelelő. Vagyis ha a körből hagyunk el élt, akkor már a gráf minden élét el kell hagynunk, azaz ezesetben csak az üres gráf felel meg. Ha viszont olyan xy élt hagyunk el a gráfból, amely nincs benne körben, akkor a gráf több komponensre esik szét: x és y különböző komponensbe kerül, mert nem megy köztük út (ha menne, az az xy éllel együtt kört zárna be). A gráf egyetlen körét csak az egyik komponens tartalmazhatja, az összes többi komponens tehát fa. Ezek minden élét el kell hagynunk, mert különben nem-üres erdőt alkotnak, s abban van elsőfokú pont. Másrészt a kört tartalmazó komponensnek sem lehet a kör pontjain kívül pontja az előző feladat előző feladat szerint. Tehát e=n esetén két megfelelő részgráf van: az üres gráf és az a feszítő gráf, amelynek élei a gráf egyetlen körének élei.

Belátható az is, hogy ha e=n+1 és a gráf összefüggő, akkor a gráfnak négy megfelelő feszítő részgráfja van. Ebben az esetben ugyanis két lehetőség van: a gráfban vagy két éldiszjunkt kör van, vagy egy kör van átlóval. Az előbbi esetben a négy megfelelő feszítő részgráf: az üres gráf, az egyik kör éleiből álló feszítő részgráf, a másik kör éleiből álló feszítő részgráf és a két kör éleiből álló feszítő részgráf. A második esetben is négy megfelelő részgráf van: az üres gráf, az a gráf, amelyiket úgy kapunk, hogy elhagyjuk az átlót és minden olyan élt, amelyiknek van a körön kívüli végpontja, és valamint az a két részgráf, amelynek élei egy-egy olyan kör élei, amely tartalmazza az átlót; ilyenből pont kettő van.

Ha még megvizsgáljuk például a négypontú teljes gráfot, abban n=4, e=6 és az üres gráfon kívül megfelelőek azok a részgráfok, amelyek egy háromszög három éléből állnak, ilyen négy van, továbbá az olyanok, amelyek egy-egy négy hosszú kör négy éléből állnak, ilyen három van. Ez összesen nyolc megfelelő feszítő részgráf.

Az ötpontú teljes gráfnak megfelelő részgráfjai az üres gráf, a tíz háromszög, az 5ˇ3=15 négyszög, a 12 ötszög, valamint azok, amelyekben van negyedfokú (telített) pont: ilyen maga a teljes gráf, ilyenek azok, amelyek két, egy pontban érintkező háromszögből állnak, ilyenből van 3ˇ5=15, továbbá azok, amelyekben két telített pont van, a másik három pontja másodfokú, ilyenből tíz van. Ez összesen 64 megfelelő részgráf, ami 2^e–n+1. Ugyanez a képlet jó az előzőleg tárgyalt esetekben is.

Az eddigi példák alapján megpróbálkozhatunk annak bizonyításával, hogy minden n pontú, de e élű összefüggő gráfnak 2^e–n+1 megfelelő részgráfja van.

1. MEGOLDÁS (Maga Péter megoldása alapján): Az e=n–1, e=n esetekben már bebizonyítottuk az állítást. Ezután adott n mellett az élszámra alkalmazunk indukciót. Ha e>n, akkor van kör a gráfban, legyen e=xy olyan él, amely benne van valamely C körben (nem hídél). Ez a C kör lesz a „váltó”, ezt fogjuk átállítani a következőképpen. Tekintsük G egy tetszőleges H részgráfját, ehhez hozzárendelünk egy másik részgráfot úgy, hogy a C kör éleit „kicseréljük”: azokat az éleit, amelyek benne vannak H-ban, elhagyjuk belőle, azokat az éleit, amelyek nincsenek H-ban, hozzávesszük H-hoz. Így minden H-hoz hozzárendelünk egy H’-t. (A hozzárendelés H’-höz H-t rendeli.) Ezzel az eljárással a kör pontjainak fokszáma páros számmal változik (vagy változatlan marad, vagy kettővel nő, vagy kettővel csökken), a többi pont fokszáma nem változik, tehát ha H megfelelő volt, H’ is az; ha H nem volt megfelelő, akkor H’ sem az. Másrészt H és H’ közül pontosan az egyik tartalmazza az e élt, s ez a G–e gráfban nem részgráf. Vagyis a megfelelő részgráfoknak pontosan a fele megfelelő G–e-ben: azok, amelyek nem tartalmazzák az xy élt. G nem-megfelelő részgráfjai közül azok, amelyek nem tartalmazzák az e élt, G–e-ben sem megfelelők, azok pedig, amelyek tartalmazzák ezt az élt, nem is részgráfjai G–e-nek. Tehát G megfelelő részgráfjainak a száma G–e részgráfjai számának pont a kétszerese. Ezzel az indukciót befejeztük.

2. MEGOLDÁS. A gráf összefüggő, tehát vegyünk egy favázát. A favázban nem szereplő élek száma e–n+1. Válasszunk ki ezek közül az élek közül egy tetszőleges E’ részhalmazt. Megmutatjuk, hogy E’ élhalmaz a faváz éleivel egyértelműen egészíthető ki úgy egy E’’ élhalmazzá, hogy minden pont foka páros legyen. Vegyük először a faváz elsőfokú pontjait: ezekről egyértelműen dönthető el, hogy a belőlük induló élt hozzá kell-e venni E’’-hoz, vagy sem: ez csak attól függ, hogy az illető elsőfokú pont (legyen a) fokszáma az E’ élhalmazban páratlan-e (ekkor a fa a-ba érkező élét hozzávesszük E’-höz), vagy páros (ekkor a fa a-ba érkező élét nem vesszük hozzá E’-höz). Ezután elhagyjuk ezeket az elsőfokú pontokat a favázból és újra megkeressük a maradó faváz elsőfokú pontjait, azokra ismét alkalmazzuk az eljárást. Az eljárást addig ismételjük, amíg az elsőfokú pontok elhagyása után már nem marad él a favázból. Ezzel beláttuk, hogy az E’ élhalmaz élei egyértelműen egészíthetők ki a faváz éleivel egy megfelelő élhalmazzá. Ilyen  E’ élhalmaz viszont pontosan 2^e–n+1 van. Ennyi megfelelő részgráf van.

3. MEGOLDÁS (Hubai Tamás megoldása): Azt, hogy az E’ élhalmaz élei egyértelműen egészíthetők ki megfelelő E’’ élhalmazzá, bebizonyíthatjuk másképp is. Először megjegyzezzük, hogy ha F és F’ megfelelő élhalmaz (tehát a gráf minden pontjának páros a foka mindkettőben), akkor megfelelő élhalmaz a kettő szimmetrikus differenciája, az F∇F’ élhalmaz is (F és F’ uniójából elhagyjuk a közös éleket). Másrészt ismert, hogy a szimmetrikus differencia művelete kommutatív és asszociatív (k halmaz szimmetrikus differenciája pontosan azokat az elemeket tartalmazza, amelyek a k halmazból páratlan sokban vannak benne).
Nevezzük a faváz éleit 1-típusú éleknek, a favázból kimaradó éleket 2-típusú éleknek. Minden 2-típusú e élhez hozzárendelhetjük azt a C_e kört, amely e-n kívül csupa 1-típusú élből áll. Ilyen kör pontosan egy van, mert a favázban e két végpontja között pontosan egy út fut. C_e nyilván megfelelő élhalmaz. Legyen most E’ a 2-típusú élek halmazának egy tetszőleges részhalmaza, ehhez rendeljük hozzá azoknak a C_e élhalmazoknak a szimmetrikus differenciáját, amelyekre e benne van E’-ben. Az üres részhalmazhoz az üres gráfot rendeljük. Így E’ minden részhalmazához egy-egy megfelelő G’ részgráfot rendeltünk. Nézzük, melyik 2-típusú élek szerepelnek ennek élhalmazában. Minden 2-típusú e él eleme C_e-nek és nem eleme egyetlen más f élhez tartozó C_f körnek sem. Tehát a szimmetrikus differenciában e pontosan akkor van benne, ha C_e szerepel azok között a körök között, amelyek szimmetrikus differenciáját képeztük. Vagyis: a kapott G’ részhalmaz a 2-típusú élek közül pontosan E’ elemeit tartalmazza. Ebből már következik, hogy bármely két különböző E’-höz tartozó G’ is különböző. Ez pontosan 2^e–n+1 megfelelő (feszítő) részgráf. Azt kell még belátnunk, hogy nincs más megfelelő részgráf. Tegyük fel, hogy van, legyen ez H. Legyen E’ azoknak a 2-típusú éleknek a halmaza, amelyek elemei H-nak. Tekintsük az E’-höz az előbb definiált G’ megfelelő részgráfot. Ekkor G’∇;H=L is megfelelő részgráf. Másrészt G’-nek is, H-nak is ugyanazok a 2-típusú élek az elemei: E’ elemei. Tehát ebben az L részgráfban nem szerepel egyetlen 2-típusú él sem, csak 1-típusú él. De azt már láttuk, hogy a faváz éleinek csak egy megfelelő részhalmaza van: az üres halmaz. Vagyis L az üres halmaz, ami azt jelenti, hogy G’ megegyezik H-val. Ez ellentmondás, vagyis valóban csak az előbb definiált 2^e–n+1 megfelelő (feszítő) részgráfja van G-nek.