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