TU Wien:Diskrete Mathematik für Informatik VU (Drmota)/Übungen WS20/Beispiel 39

How many colours do you need to colour the edges (!) of a complete graph, such that no two incident edges have the same colour? (www.findstat.org/St000271 may be interesting to look at) Hint: label the vertices 0 to n - 1 and consider the sum of the vertices connected by an edge.

Hilfreiches

Edge Colouring

Lösungsvorschlag

As we have a complete graph, no independent set can contain more than (n-1)/2 edges. Give the vertices the labels 0, ..., n-1. There are two cases:
n is odd
Let $S_{p}=\{(p-q,p+q)|q=1,2,...(n-1)/2\}$ for p = 0, 1, ... n-1. (p-q,p+q) describes an edge in the graph. (p-q), (p+q) is expressed as 0, 1, ... n-1 modulo n-1. $S_{p}$ is independent. Every edge in the graph is in one of the sets --> The union of all $S_{p}$ with $p\in 0,...,n-1$ is the Edge Set. We have n independent sets --> we need n colours.
n is even (for n>=4, n=2 is trivial)
Take the (complete) graph $K_{n-1}$ as $K_{n}$ and remove vertex n (and the incident edges). We have as described above the independent set $S_{p}$. Create the new sets $T_{p}$: $T_{p}=S_{p}\cup (\{p,n\})$ where n is the removed vertex. As shown above, for $K_{n}-1$ we have n-1 colours, but every vertex has a degree of n-1 --> at each vertex there is an edge colour "left over", which can be used for (p,n) --> n-1 colours.

See also https://www.math.ru.nl/OpenGraphProblems/Gerjan/Behzad%20Chartrand%20Cooper.pdf