Question

G is a simple undirected graph and some vertices of G are of odd degree. Add a node n to G and make it adjacent to each odd degree vertex of G. The resultant graph is ______

(a) Complete bipartite graph

(b) Hamiltonian cycle

(c) Regular graph

(d) Euler graph

I got this question in an interview.

I would like to ask this question from Complete and Connected Graphs in portion Graphs of Discrete Mathematics

Answer 1

The correct choice is (d) Euler graph

The best I can explain: In any simple undirected graph, total degree of all vertices is even (since each edge contributes 2 degrees). So number of vertices having odd degrees must be even, otherwise, their sum would have been odd, making total degree also odd. Now single vertex n is connected to all these even number of vertices (which have odd degrees). So, degree of n is also even. Moreover, now degree of all vertices which are connected to v is increased by 1, hence earlier vertices which had odd degree now have even degree. So now, all vertices in the graph have even degree, which is necessary and sufficient condition for euler graph.