Question

G is a simple, connected, 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

Answer 1

The correct option is D Euler

In an undirected simple, connected graph number of vertices must be even of odd degree (using Handshaking lemma).

Adding a vertex v, adjacent to all odd degree vertices in graph, so degree of all odd degree vertices now become even and degree of vertex v is also even (since number of odd degree vertex are even).

Now all vertices in the graph are of even degree and graph is connected, so it must be Eular graph.