6 For which n does the complete graph Kn admit an Euler circ

6. For which n does the complete graph K_n admit an Euler circuit?

Solution

We know that Kn is an undirected multigraph and an undirect multigraph has a Euler circuit if and only if it is connected and all the vertices have even valence. Therefore we will try to figure out Kn when each of its vertices have even valence.

We know that if Kn has n vertices then it will have n(n-1)/2 edges. if the total number of valences in Kn are divided by n then the outcome will be an even number and therefore, Kn will have an Euler circuit. Furthermore, we know that the number of valences in a graph is two times the number of edges in that graph. Therefore, if the number of edges in Kn are n(n-1), then the number of valences in Kn will be n(n-1).

We can get the valence of each vertex by dividing the total number of valences of Kn by the number of vertices.

Therefore, valence of each vertex = n(n-1)/n = (n-1)

Therefore valence of each vertex is (n-1). For (n-1) to be even, n must be an odd number. Therefore, for Kn to have Euler circuit, n must be an odd number.