Nerovinnost Petersenova grafu
Úloha číslo: 4109
Dokažte dvěma způsoby, že Petersenův graf není rovinný.
Řešení
První způsob – s využitím Kuratowského věty, protože obsahuje dělení \(K_{3{,}3}\)
Druhý způsob: kontrakce zachovávají rovinnost, ale kontrakcí párování mezi vnějším a vnitřním pěticyklem získáme nerovinný graf \(K_5\).
Třetí způsob: Petersenův graf nemá trojúhelníky ani čtyřcykly. Pokud by byl rovinný, měl by jako důsledek Eulerovy formule splňovat odhad \(|E_P|\le \frac53(|V_P|-2)\), což ale nesplňuje.
