Question

Assume G is a simple undirected graph and 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, then the resultant graph is sure to be _______.

• A. Euler
• B. Complete
• C. Hamiltonian
• D. Clique

Hint:

For a graph to be Eulerian, all its vertices must have even degrees. Adding a vertex to connect all odd-degree vertices ensures this property.

Answer 1

The Correct Option is A

By adding a node \( v \) and connecting it to all vertices with an odd degree, we are ensuring that all vertices in the resultant graph have an even degree. 
A graph in which all vertices have even degrees is Eulerian, meaning it has an Eulerian circuit (a closed path that uses each edge exactly once). 
Thus, the resultant graph is Eulerian. Hence, the correct answer is option (1).