Hranová barevnost úplného grafu

Určete chromatický index, neboli hranovou barevnost, úplného grafu \(K_n\).

Nápověda
Rozlište případy sudého a lichého \(n\).
Řešení
Pro sudé \(n\) si vrcholy grafu nakreslíme do vrcholů pravidelného \((n-1)\)-úhelníku a poslední vrchol umístíme do jeho středu. Libovolnou hranu vedoucí ze středu na okraj lze rozšířit na perfektní párování tak, že přidané hrany jsou kolmé na výchozí hranu.

Tato párování jsou navzájem disjunktní a dokazují, že \(\chi’(K_n)=\Delta(K_n)=n-1\), viz obrázek.

Pro liché \(n\) si všimneme, v každém maximálním párování zůstane jeden vrchol nepokrytý. Proto má každé maximální párování \(\frac{n-1}{2}\) hran. Graf \(K_n\) má celkem \(\frac{n(n-1)}{2}\) hran, tedy každé hranové obarvení musí mít alespoň \(n\) tříd.

Protože je \(K_n\) podgrafem \(K_{n+1}\), platí \(\chi’(K_n)\leq \chi’(K_{n+1})=n\).
Odpověď
Chromatický index úplného grafu \(K_n\) je \( \chi(K_n)= \begin{cases} n-1 & n \text{ je sudé}\\ n & n \text{ je liché} \end{cases} \).