Mathematics. Graph..........?

Question

The compliment of a graph G is a having the same vertex set as G but consisting of exactly those edges that are not edges of G. ( If AB is an edge of G, then it is not an edge in the compliment and vice versa. Let N denotes the number of vertices in G.
a) Suppose N is even (N is greater than or equal to 4) and G has an Euler Circuit. Explain why the compliment of G can not have an Euler circuit.
b) Suppose N is odd (N is greater than or equal to 5) and has an Euler circuit. Explain why the compliment of G may or may not have not have a Euler circuit.

Answer 1

Just to start you off, a graph G can have an Euler Circuit if and only if every vertex is of even degree.

If the number of vertices N is even, then there are N-1 (an odd number) of possible edges from any vertex V. If G contains an even number of edges from V, then its complement ...