Matematické Fórum

Dobrý den,

prosím o kontrolu řešení příkladu z teorie grafů, pro přesnost vkládám zadání přímo ze skript ve slovenštině:

Dokážte, že ak súvislý graf G s n ≥ 6 vrcholmi obsahuje tri kostry také, že každá z hrán grafu G patrí práve do jednej z nich, tak G nie je planárny.

Moje řešení:
Nejprve definice:
1) Graf je souvislý, pokud libovolné dva vrcholy grafu souvislé (="lze je spojit")
2) Kostra grafu G = (V, E) je faktorový podgraf T[mathjax]\subseteq[/mathjax]G grafu G, který je stromem (=souvislý graf, který neobsahuje kružnici). Strom T je tak kostrou grafu G, jestli je podmnožinou G a zároveň má T a G stejný počet vrcholů.
3) Graf G je planární, jestliže existuje takové zakreslení v rovině takové, že se jeho hrany protínají pouze v koncových vrcholech. Z obrázku se dá poznat podle Kuratowského věty – nesmí obsahovat podgraf izomorfní s [mathjax]K_5[/mathjax]  ("úplný graf s pěti vrcholy") nebo [mathjax]K_{3,3}[/mathjax] (bipartitní graf s dvěma podmnožinami po třech vrcholech)

Dále:
a) Pro planární graf platí Eulerův vzorec: |V|-|E|+s=2 (s...počet stěn)
b) Pro stromy platí: |V|=|E|+1

Proto mě napadlo, že když vycházím z b) a 2), počet vrcholů takového grafu můžu vyjádřit jako 3*(|E|+1). Dosadím do Eulerova vzorce:
3*(|E|+1) - |E| + s =2
2|E| + s = -1
A protože součet počtu hran a stěn nemůže vyjít záporné číslo a neplatí tedy Eulerův vzorec, graf nemůže být planární.

Je má úvaha prosím správná? Předem díky za pomoc!