Nerovinnost úplného grafu
Úloha číslo: 4110
Bez použití Kuratowského věty dokažte, že graf \(K_5\) není rovinný.
Nápověda
Kolik hran může mít rovinný graf?
Řešení
Rovinný graf s \(n\) vrcholy může mít nejvýše \(3n-6\) hran. S pěti vrcholy tedy nejvýše devět hran. Úplný graf \(K_5\) jich má ale \(10\).
