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

Let ${\displaystyle 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. ${\displaystyle S_{p}}$ is independent. Every edge in the graph is in one of the sets --> The union of all ${\displaystyle S_{p}}$ with ${\displaystyle p\in 0,...,n-1}$ is the Edge Set. We have n independent sets --> we need n colours.
Take the (complete) graph ${\displaystyle K_{n-1}}$ as ${\displaystyle K_{n}}$ and remove vertex n (and the incident edges). We have as described above the independent set ${\displaystyle S_{p}}$. Create the new sets ${\displaystyle T_{p}}$: ${\displaystyle T_{p}=S_{p}\cup (\{p,n\})}$ where n is the removed vertex. As shown above, for ${\displaystyle 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.