Elegendő belátni a következő állítást:

Lemma: Ha egy gráf páratlan fokú pontjai által alkotott Q ponthalmaz nem üres, akkor ennek található két eleme x,y úgy, hogy úttal összeköthetőek legyenek G-ben.

A lemmából következik állításunk: út éleit elhagyjuk és állításunkat iteráltan alkalmazzuk: A lemma garantál egy x₁ és y₁ csúcsot és köztük U₁ utat. Hagyjuk el G-ből U₁ éleit. Legyen G₁ az így kapott gráf. G₁ páratlan fokú pontjainak halmaza Q-{x₁,y₁}. Ha ez nem ü'res a lemma garantálja x₂ és y₂ elemeit és köztük U₂ utat. Ezen út éleinek elhagyása vezessen el a G₂ gráfhoz, amely páratlan fokú csúcsainak halmaza Q-{x₁,x₂,y₁,y₂}. És így tovább. Az így kapott U₁,U₂,U₃,... útsorozat elemei egymástól éldiszjunktak lesznek és bizonyítják állításunkat.

Lemma 1. bizonyítása Legyen x a Q halmaz egy tetszőleges eleme. x meghatározza G egy komponensét, amelyben lennie egy másik páratlan fokú pontnak (Q egy másik elemének). Az egy komponensben lévő x és y pontok között egy P útnak.

Lemma 2. bizonyítása Legyen x a Q halmaz egy tetszőleges eleme. x-ből egy mohó vonalnövelést végezve eljárásunk Q egy másik pontjában akadhat el. Ez a vonal tartalmaz egy megfelelő P utat.

Vissza