Answer to Question #186267 in Discrete Mathematics for Gazal Gulati

Question

Find the edge chromatic

numbers to colour the edges of the complete graph with four and five vertices

Answer 1

1. The edges of the complete graph with 4 vertices can not be colored in 2 colours.

All the edges 12, 13, 14 are adjacent to one another, so they must have different colours. Therefore, the number of colour must be 3 or greater.

2. The edges of the complete graph with 4 vertices can be colored in 3 colours.

Example. Let 1, 2, 3, 4 denote the vertices of the graph. Then we can color the edges 12, 34 in green, 13, 24 in red, and 14, 23 in blue. It can be seen directly that the edges of the same colour have no common vertices. Therefore, this coloring is acceptable.

Combining the results of (1) and (2), we obtain that the edge chromatic numbers to colour the edges of the complete graph with 4 vertices is 3.

3. The edges of the complete graph with 5 vertices can not be colored in 4 colours.

The complete graph with 5 vertices contains 10 edges. Suppose that this graph can be colored in 4 colours. Then one of colours is used to color at least 3 different edges (otherwise the total number of edges must be not greater than $4\cdot2 =8$). But the edges of the same colour must not be adjacent to each other. Therefore the total number of the different vertices, which are connected by these edges, is 6 or greater. From the obtained contradiction we conclude that the number of colours must be 5 or greater.

4. The edges of the complete graph with 5 vertices can be colored in 5 colours.

Let 1, 2, 3, 4, 5 denote the vertices of the graph. Then we can color the edges 12, 34 in green, 23, 45 in red, 15, 24 in yellow, 25, 13 in orange and 14, 35 in blue. It can be seen directly that the edges of the same colour have no common vertices. Therefore, this coloring is acceptable.

Combining the results of (3) and (4), we obtain that the edge chromatic numbers to colour the edges of the complete graph with 5 vertices is 5.