Graph Theory Lessons

Suppose instead of coloring the vertices of a graph we color the edges. If we color the edges so that edges with a common end vertex have different colors and we use as few colors as possible we get a proper edge coloring. The number of colors used in a proper edge coloring of a graph is called the chromatic index of the graph. We use the notation Χ'(G) for the chromatic index of the graph G.

Fig 15.2, A proper edge coloring of the cube

We now turn our attention to the complete graphs with an odd number of vertices. The next question is very easy if you did the previous ones.

The pidgeonhole principle . is as follows: If m pidgeons occupy n pidgeonholes and m > n then at least one pidgeonhole contains two or more pidgeons.
You probably don't spend your time watching pidgeons so think of it like this: If you have m students living in a dorm with n rooms and if m > n then at least one room has two or more residents.

Now suppose you have ninety students and only twenty dorm rooms. Then one can see that at least one room will have five or more students because four in each room would only account for eighty students. We are not going to talk only about pidgeons or students. In general if you have m items and you assign each item to one of n categories and m > n there will be at least two items of the same category.

We shall now prove that the chromatic index of K₅ is 5. You will prove the general case for K_2n-1 in the next question.
We have already shown that the edges of K_2n-1 can be properly colored using 2n - 1 colors so we have that the edges of K₅ can be properly colored using 5 colors. We also know that the vertices of K₅ have degree 4 so we cannot color the edges properly with less than 4 colors. We therefore only have to show that the edges of K₅ can not be properly colored using 4 colors.

Suppose to the contrary that we can color the (1/2)*5*4 = 10 edges of K₅ properly using four colors. If you think of the edges as the items and the colors as the categories then by the pidgeonhole principle there is at least one color that is used on ⌈10/4⌉ = 3 or more edges. Take three edges of the same color. They have six endpoints. Again, using the pidgeonhole principle it means, since K₅ has only five vertices, that there is a vertex that is the endpoint of at least two edges of the same color. (Here the "items" are the six endpoints and the "categories" are the five vertices of K₅).This contradicts the assumption that it is a proper edge coloring and so we can't color K₅ using four colors. Therefore the chromatic index of K₅ is 5.