Chromatic index of complete graph

Task number: 4066

Determine the chromatic index, i.e. the edge chromatic number, of the complete graph \( K_n \).

  • Hint

    Distinguish the cases of even and odd \( n \).

  • Solution

    For even \( n \), draw the vertices of the graph into the vertices of a regular \( (n-1) \) -gon and place the last vertex in its center. Any edge leading from center to the boundary can be extended to a perfect matching so that the added edges are perpendicular to the starting edge.

    These matchings are disjoint to each other and prove that \( \chi’(K_n) = \Delta (K_n) = n-1 \), see figure.

    Edge coloring of K7

    For odd \( n \) we notice that in each maximum matching, one vertex remains uncovered. Therefore, each maximum matching has \( \frac{n-1}{2} \) edges. The graph \( K_n \) has a total of \( \frac{n (n-1)}{2} \) edges, so each edge coloring must have at least \( n \) classes.

    Since \( K_n \) is a subgraph of \( K_{n + 1} \), we get \( \chi'(K_n) \leq \chi' (K_{n + 1}) = n \).

  • Answer

    The chromatic index of the complete graph \( K_n \) is \( \chi (K_n) = \begin{cases} n-1 & n \text{ is even} \\ n & n \text{ is odd} \end{cases} \).

Difficulty level: Moderate task
Proving or derivation task
Solution require uncommon idea
Cs translation
Send comment on task by email