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.

Dieses Beispiel hat einen unbekannten Lösungsstatus. Bitte editiere diese Seite und schreibe den dir bekannten Status ins Beispiel. Die möglichen Werte sind hier: Vorlage:Beispiel dokumentiert. Führe folgende Änderung durch:

{{Beispiel|1=
Angabetext
}}

oder

{{Beispiel|
Angabetext
}}

zu (im Falle einer korrekten, unverifizierten Lösung "solved". Auch möglich "unsolved", "wrong", "verified_by_tutor". Alle möglichen Werte sind hier: Vorlage:Beispiel dokumentiert.)

{{Beispiel|status=solved|1=
Angabetext
}}

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