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**
Show answer & explanation
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.