Úplné grafy na toru

Úloha číslo: 3273

Které úplné grafy \(K_n\) lze vnořit, t.j. nakreslit bez křížení hran, na torus?

  • Nápověda

    Využijte Eulerovou formuli pro torus.

    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\). Torus má \(g = 2\). Dosazením získáváme: \[ \begin{eqnarray*} |V| + |F| &=& |E| + 2 - g \\ |V| + \frac{2}{3} |E|&\geq& |E| \\ 6|V| + 4|E| &\geq& 6|E| \\ 6|V| - 2|E| &\geq& 0\\ 6n -n^2 + n &\geq& 0 \\ n^2 -7n &\leq& 0 \\ (n-7) &\leq& 0 \\ \end{eqnarray*} \]

    Řešení přes Heawoodovu formuli:

    Projektivní rovina má Eulerovu charakteristiku \(\chi = 0\) a Heawoodova mez vychází \(h(\chi) = \lfloor (7 + \sqrt{49-24{\cdot} 0})/2 \rfloor= 7\)

    V obou případech vyšla horní mez 7, tedy grafy větší než \(K_7\) nelze vnořit. Nakreslit \(K_7\) lze například tak, že nejprve se nakreslí cyklus \(C_6\), tak abychom dovnitř mohli přidat univerzální vrchol, jako na obrázku.

    K7 na toru
  • Odpověď

    Největší úplný graf, který lze nakreslit na torus, je \( K_7 \).

Obtížnost: Snadná úloha (řešená úvahou nebo přímo z definic)
Úloha řešená úvahou
Úloha vyžadující neobvyklý trik nebo nápad
En translation
	Zaslat komentář k úloze