Grafy se sudými stupni

Úloha číslo: 3623

Dokažte, že graf se všemi stupni sudými neobsahuje most, tedy hranu, jejímž odebráním se zvýší počet komponent.

  • Řešení

    Patří-li hrana \(e\) komponentě \(C\), potom po odebrání \(e\) zůstanou ostatní komponenty beze změny. Jediný případ, kdy by se odebráním \(e\) mohl zvýšit počet komponent, by mohl nastat v situaci, kdy by se \(C\) rozpadlo na více částí.

    Komponenta \(C\) sama o sobě indukuje souvislý graf se sudými stupni, tedy tato komponenta má uzavřený eulerovský tah. Tento tah lze zvolit tak, že \(e\) je jeho poslední hranou. Po odebrání \(e\) zůstane v \(C\) otevřený eulerovský tah, z jehož existence ovšem plyne, že se komponenta \(C\) nerozpadne na dvě části, čili že zůstane souvislá.

    Proto \(e\) nemůže být mostem.

Obtížnost: Snadná úloha (řešená úvahou nebo přímo z definic)
Úloha na dokazování, ověřování
En translation
	Zaslat komentář k úloze