Construct a graph $G$ as follows: The vertices of $G$ are the edges of a complete graph $K_5$ on 5 vertices. The vertices of G are adjacent if and only if the corresponding edges of $K_5$ have an endpoint in common. Determine the chromatic number of this graph.
$\endgroup$2 Answers
$\begingroup$Your problem is equivalent to finding a proper edge coloring of $K_5$.
Since your are dealing with a complete graph with an odd number of vertices, you need exactly $5$ colors.
$\endgroup$ $\begingroup$The line graph of $G=(V,E)$, denoted by $L(G)$, is defined to be the graph with vertex set $E$, and two edges $e, f \in E$ are adjacent vertices in $L(G)$ whenever $e$ and $f$ are incident in $G$. Observe that the edge-coloring number (aka chromatic index) of $G$ is equal to the chromatic number of $L(G)$.
Thus, you are looking for the edge-chromatic number (aka chromatic index) of $K_5$, which is equal to the chromatic number of its line graph $L(K_5)$. This value is the smallest size of a partition of the edge set of $K_5$ into matchings. Any matching of $K_5$ has at most 2 edges. $K_5$ has 10 edges, and so any partition of the edge set of $K_5$ into matchings has size at least 5.
It can be proved that the chromatic index of $K_n$ is $n$ if $n$ is odd.
$\endgroup$
