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.)