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

From VoWi
Jump to navigation Jump to search

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[edit | edit source]

Edge Colouring

Lösungsvorschlag[edit | edit source]

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 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. is independent. Every edge in the graph is in one of the sets --> The union of all with 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 as and remove vertex n (and the incident edges). We have as described above the independent set . Create the new sets : where n is the removed vertex. As shown above, for 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