Coloring Complete Graph

Question

Let $n$ be a positive odd integer. There are $n$ computers and exactly one cable joining each pair of computers. You are to colour the computers and cables such that no two computers have the same colour, no two cables joined to a common computer have the same colour, and no computer is assigned the same colour as any cable joined to it. Prove that this can be done using $n$ colours.

Here is how I translated it into a graph:

Call the graph $G$. Note that $G$ is a complete graph. We would like to prove that using $n$ colors, we can color every vertex a different color and no two edges coming out of a single vertex is the same color, and no vertex and edge connecting the vertex is the same color either.

I wanted to prove this problem using construction, but I'm not sure how to. I know that you color every vertex a different color, and you have to prove that you can have each vertex have $n-1$ edges incident to it which together with the vertex's color, is the set of all colors, but I'm lost.

Thank you!

Answer 1

Arrange the computers in a circle & Rotate the configuration above.

Answer 2

Identify the vertices of $K_n$ with the vertices of a regular $n$-gon. Give each vertex a different colour. For any two vertices $x\ne y$, since $n$ is odd, the perpendicular bisector of the line segment $xy$ passes through a unique vertex $z$. Give the edge $xy$ the same colour as the vertex $z$.

Alternatively label the vertices $0,1,\dots,n-1$. Give each vertex a different colour. For any two vertices $x\ne y$, since $n$ is odd, there is a unique $z\in\{0,1,\dots,n-1\}$ such that $x+y\equiv2z\pmod n$; give the edge $xy$ the same colour as the vertex $z$.

We have shown that, for odd $n$, the total chromatic number of $K_n$ is $n$. This is equivalent to the fact that, for even $n$, the edge chromatic number of $K_n$ is $n-1$. Suppose $n$ is odd, and suppose we have a (proper) edge colouring of $K_{n+1}$ with $n$ colours. To get a total colouring of $K_n$ with the same colours, delete any vertex $v$, and give each remaining vertex $x$ the same colour that was given to the edge $vx$.