Nerovinnost Petersenova grafu

Úloha číslo: 4109

Dokažte dvěma způsoby, že Petersenův graf není rovinný.

Petersenův graf
  • Řešení

    První způsob – s využitím Kuratowského věty, protože obsahuje dělení \(K_{3{,}3}\)

    Dělení K_33

    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.

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