Give a general statement about when a complete graph Kn will

Give a general statement about when a complete graph, K_n, will have an Euler cycle (e.g. complete graph will have an Euler cycle when n is). Give a general statement about when bipartite graph, K_m,n, will have an Euler cycle, (e g bipartite graph will have an Euler cycle if and only if

Solution

When N is odd. (Every vertex in K_N has degree N 1, so we need N 1 to be even.)

note: We know that a graph has an Euler cycle if and only if all its degrees are even.

As noted above, Km,n has vertices of degree m and n, so it has an Euler cycle if and only if both m and n are even.