Indukovaný cyklus

Úloha číslo: 3579

Ukažte, že když \(G\) obsahuje lichý cyklus jako podgraf, tak potom obsahuje také nějaký lichý cyklus jako indukovaný podgraf.

  • Řešení

    Sporem ukážeme, že nejkratší lichý cyklus je nutně indukovaný.

    Nechť \(C\) je lichý cyklus v \(G\), který není indukovaný. Potom obsahuje příčku, která daný cyklus rozděluje na dva kratší cykly. Jeden z nich je lichý, spor.

    (Využíváme fakt: Je-li průnik dvou cyklů stejné parity cesta, potom symetrická diference množin hran těchto cyklů určuje sudý cyklus.)

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