Kritický nerovinný a odebírání hrany

Úloha číslo: 3278

Nechť \(G\) je nerovinný graf takový, že \(G - e\) je rovinný pro každou hranu \(e\) grafu \(G\). Obsahuje pak nutně \(G\) hranu \(e\) takovou, ze \(G-e\) je maximální rovinný graf, tj. přidáním libovolné hrany \(f\), graf \(G-e+f\) bude nerovinný?

  • Nápověda

    Zkuste najít protipříklad.

  • Řešení

    Tvrzení neplatí. Protipříklad je například graf \(K_{3{,}3}\).

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