Feladat: N.72 Korcsoport: 18- Nehézségi fok: nehéz
Megoldó(k):  Braun Gábor ,  Burcsi Péter ,  Gyarmati Katalin ,  Valkó Benedek 
Füzet: 1996/április, 228 - 229. oldal  PDF file
Témakör(ök): Páros gráfok, Nehéz feladat
Hivatkozás(ok):Feladatok: 1995/május: N.72

Bizonyítandó, hogy tetszőleges G egyszerű gráf pontjai két diszjunkt részre oszthatók úgy, hogy a két rész között futó éleket elhagyva egy olyan G' gráfot kapunk, amelynek minden csúcsából páros sok él indul ki.

A szöveg csak Firefox böngészőben jelenik meg helyesen. Használja a fenti PDF file-ra mutató link-et a letöltésre.

A gráf csúcsainak számára vonatkozó teljes indukcióval bizonyítunk. Ha G minden csúcsából páros sok él indul ki, akkor az állítás nyilvánvaló, ui. a csúcsokat véve az egyik résznek, az üres halmazt véve a másik résznek a kívánt felosztást kapjuk, hiszen G'=G megfelelő. Ide tartozik az 1 csúcsú egyszerű gráf esete is, aminek nincsen éle.
Tegyük fel, hogy n csúcsú gráfokra már beláttuk az állítást; bizonyítsuk be az n+1 csúcsú G gráfra is. Feltehetjük, hogy G-nek van legalább egy páratlan fokú P pontja. Legyenek a P szomszédai A1, A2, ..., A2k+1. A G-ből hagyjuk el a P-t és a belőle induló éleket, továbbá, ha Ai-t és Aj-t él köti össze, akkor ezt az élt is hagyjuk el; ha pedig nem köti őket össze él, akkor kössük őket össze éllel. Jelöljük az így kapott gráfot G1-gyel.
G1  n csúcsú egyszerű gráf, ezért az indukciós feltétel szerint pontjai két diszjunkt H1 és H2 részre oszthatók úgy, hogy az ezek közt futó élek elhagyásával keletkező G1' gráf minden pontjának foka páros. A H1 és H2 részek közül az egyikben páros, a másikban páratlan számú szerepel az A1,A2,...,A2k+1 pontokból. Az általánosság csorbítása nélkül feltehetjük, hogy H1-ben az A1,A2,...,A2l, H2-ben az A2l+1,A2l+2,...,A2k+1 csúcsok szerepelnek. A G pontjait osszuk a H1{P} és H2 diszjunkt részekre, és legyen G' a két rész közti élek elhagyásával keletkező gráf. Állítjuk, hogy G' minden pontjának foka páros, ami igazolja a feladat állítását.
G'-ben a P szomszédai az A1,A2,...,A2l pontok, P foka tehát páros. A P-től és az Ai-ktől különböző csúcsoknak a G'-ben ugyanazok a szomszédai, mint G1'-ben, tehát az ilyen csúcsok foka is páros G'-ben. Már csak az Ai csúcsok fokszámáról kell belátnunk, hogy párosak.
Tekintsünk egy Ai csúcsot, legyen ennek foka a G1'-ben k1, a G'-ben pedig k. Mivel k1 páros, azért elegendő igazolnunk, hogy k+k1 páros. Ha Ai H1-beli, akkor G'- és G1'-beli szomszédainak együttes számbavételénél a H1{A1,A2,...,A2l}-be eső szomszédokat pontosan kétszer, az {A1,A2,...,Ai-1,Ai+1,...,A2l;P}-be esőket pontosan egyszer számoltuk. Ezért k+k1 (két páros szám összegeként) páros. Hasonlóan, ha Ai H2-beli, akkor G'- és G1'-beli szomszédainak együttes számbavételénél a H1{A2l+1,A2l+2,...,A2k+1}-be eső szomszédokat pontosan kétszer, az {A2l+1,A2l+2,...,Ai-1,Ai+1,...,A2k+1}-be esőket pontosan egyszer számoltuk. Tehát k+k1 (megint csak két páros szám összegeként) páros.
Ezzel a feladat állítását bebizonyítottuk.

 Braun Gábor (Budapest, Szent István Gimn., II. o. t.)