G is a simple undirected graph. Some vertices of G are of odd degree. Add a node v to G and make it adjacent to each odd...

Question

G is a simple undirected graph. Some vertices of G are of odd degree. Add a node v to G and make it adjacent to each odd degree vertex of G. The resultant graph is sure to be

A. regular
B. complete
C. Hamiltonian
D. Euler

Accepted Answer

Euler An Eulerian graph has an Eulerian circuit (closed walk visiting every edge once). The condition: every vertex must have even degree. In any undirected graph, the count of odd-degree vertices is always even (handshaking lemma). Adding vertex v adjacent to all k odd-degree vertices: each odd-degree vertex gains 1 edge (odd + 1 = even), and v gets degree k (even). So all vertices in the augmented graph have even degree, making it Eulerian.

G is a simple undirected graph. Some vertices of G are of odd degree. Add a node v to G and make it adjacent to each odd degree vertex of G. The resultant graph is sure to be A. regular B. complete C. Hamiltonian D. Euler