OA. free
Free
Optym Core Computer Science Core Computer Science Medium

Number of vertices with odd degrees in a graph having a eulerian walk

Optym technical mcq question, verified with a worked answer. Free to practise - no sign-up.

Number of vertices with odd degrees in a graph having a eulerian walk**

Choose one option.
Show answer & explanation
Answer: A. A) 0 or 2

By Euler's theorem, an undirected connected graph contains an Eulerian path (walk) if and only if the number of vertices with odd degree is either 0 (an Eulerian circuit) or exactly 2 (the start and end points of the walk).

Step-by-step Derivation:
Step 1: In an Eulerian trail, every edge is visited exactly once.
Step 2: Each intermediate vertex must be entered and exited an equal number of times, contributing an even degree.
Step 3: If start and end vertices are identical, all vertices have even degree (0 odd vertices).
Step 4: If start and end vertices are distinct, only the start and end vertices have odd degree (2 odd vertices).
Step 5: Thus, the number of odd-degree vertices is 0 or 2.