Ú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.

    K6 v projektivní rovině
  • Odpověď

    Největší úplný graf, který lze nakreslit do projektivní roviny, je \( K_6 \).

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