Questions: Eulerian Paths, Circuits, and Characterization

Question 1

A city planner wants to design a snow plow route that covers every road exactly once and returns to the starting depot. What must be true of the graph representing the street network?

• A. The graph must be a tree with no cycles
• B. Every vertex must have degree at least 2
• C. Exactly two vertices must have odd degree
• D. Every vertex must have even degree

Answer: (D)

A route that traverses every edge exactly once and returns to the start is an Eulerian circuit, which exists if and only if every vertex has even degree. The reasoning: every time you enter an intersection on one road, you must leave on a different road, using edges in pairs. Only if all edges pair up perfectly (even degree everywhere) can you return to the start without getting stuck. Option C describes the condition for an Eulerian path (not a circuit) — it would allow a route with different start and end points.

Question 2

A connected graph has 8 vertices with degrees 4, 3, 2, 3, 2, 4, 2, 3. Does this graph have an Eulerian circuit, an Eulerian path, or neither?

• A. Eulerian circuit, since the graph is connected and most vertices have even degree
• B. Eulerian path from one odd-degree vertex to another
• C. Neither — it has more than two vertices of odd degree
• D. Eulerian path, since the sum of all degrees is even

Answer: (C)

Counting odd-degree vertices: 3 (odd), 3 (odd), 3 (odd) — three odd-degree vertices. The degree condition requires exactly 0 odd-degree vertices for a circuit or exactly 2 for a path. Three odd-degree vertices satisfies neither condition, so no Eulerian path or circuit exists. Option A commits the common error of assuming connectivity is sufficient. Option D is a red herring: the sum of degrees is always even (by the handshake lemma), but that tells you nothing about the Eulerian condition.

Question 3

An Eulerian path visits nearly every vertex exactly once, while an Eulerian circuit also returns to the starting vertex.

• T. True
• F. False

Answer: False

This confuses Eulerian paths with Hamiltonian paths. An Eulerian path traverses every EDGE exactly once — it may revisit vertices freely. A Hamiltonian path visits every VERTEX exactly once. The distinction is crucial: Eulerian conditions are easy to check (count odd-degree vertices) and can be solved efficiently, while Hamiltonian conditions are NP-complete in general.

Question 4

If a connected graph has exactly two vertices of odd degree, those two vertices must be the endpoints (start and finish) of any Eulerian path in that graph.

• T. True
• F. False

Answer: True

The logic is necessary: every vertex that is merely passed through uses its edges in pairs (one in, one out), requiring even degree. The start vertex contributes one extra edge leaving without entering, and the end vertex contributes one extra edge entering without leaving — both must have odd degree. With exactly two odd-degree vertices, these are forced to be the start and end, with no choice in the matter.

Question 5

Why does a vertex in the middle of an Eulerian path require even degree, while the starting and ending vertices are allowed to have odd degree?

Model answer: A vertex in the middle of the path is entered and exited repeatedly — each entry uses one edge and each exit uses another, so edges are consumed in enter/exit pairs. This requires the vertex to have even degree. The starting vertex is left initially without being entered first (one edge used before any pairing begins), and the ending vertex is entered last without being exited (one edge used after pairing ends). Each contributes exactly one 'unpaired' edge, giving both odd degree.

This degree-parity argument is the key insight of Eulerian characterization. The condition is not just a fact to memorize — it follows directly from the enter/exit pairing logic at each vertex. Understanding this argument also explains why the condition is both necessary and sufficient, and why exactly 0 or 2 odd-degree vertices are the only possibilities that permit an Eulerian traversal.