Úplné grafy v projektivní rovině
Úloha číslo: 3272
Které úplné grafy \(K_n\) lze vnořit, t.j. nakreslit bez křížení hran, do projektivní roviny?
Nápověda
Využijte Eulerovou formuli pro projektivní rovinu.
Alternativně lze vyjít z Heawoodovy formule.
Řešení
Řešení přes Eulerovu formuli:
Pro \(K_n\) platí: \(|V|(|V|-1) = 2|E|\) a \(|F| \leq \frac{2}{3}|E|\). Eulerova formula pro plochy vyššího rodu zní: \(|V| + |F| = |E| + 2 - g\). Projektivní rovina má \(g = 1\). Dosazením získáváme: \[\begin{eqnarray*} |V| + |F| &=& |E| + 2 - g \\ |V| + \frac{2}{3} |E|&\geq& |E| + 1 \\ 6|V| + 4|E| &\geq& 6|E| + 6\\ 6|V| - 2|E| &\geq& 6\\ 6n -n^2 + n &\geq& 6 \\ n^2 -7n + 6 &\leq& 0 \\ (n-6)(n-1) &\leq& 0 \\ n &\leq& 6 \\ \end{eqnarray*}\]
Řešení přes Heawoodovu formuli:
Projektivní rovina má Eulerovu charakteristiku \(\chi = 1\) a Heawoodova mez vychází \(h(\chi) = \lfloor (7 + \sqrt{49-24})/2 \rfloor= 6\)
V obou případech vyšla horní mez 6, tedy grafy větší než \(K_6\) nelze vnořit. Nakreslit \(K_6\) lze například tak, že nejprve se nakreslí úplný graf \(K_5\), tak aby měl cross-cap uvnitř a vnější stěna měla délku 5, jako na obrázku vlevo. Vpravo je pak nakreslení po kruhové inverzi cros-scapu.
Odpověď
Největší úplný graf, který lze nakreslit do projektivní roviny, je \( K_6 \).