Questions: Euler Paths, Euler Circuits, and Applications

Question 1

A connected road network has every intersection at even degree except two: the library and the post office. What can be concluded about Euler paths and circuits in this network?

• A. An Euler circuit exists starting and ending at any intersection.
• B. An Euler path exists from the library to the post office, but no Euler circuit exists.
• C. An Euler path exists between any two odd-degree vertices, not just the library and post office.
• D. Neither an Euler path nor an Euler circuit exists because there are vertices with odd degree.

Answer: (B)

Exactly two odd-degree vertices is the precise condition for an Euler path — and the path must start at one odd-degree vertex and end at the other. Since the two odd-degree vertices are the library and post office, an Euler path connects them. No Euler circuit exists because a circuit requires *all* even-degree vertices. Option D is wrong because odd-degree vertices don't prevent an Euler path — they just determine its endpoints.

Question 2

In the Chinese postman problem, a mail carrier must traverse every street at least once and return to the start. The route graph has four vertices with odd degree. Why must the carrier repeat some streets?

• A. Postal regulations require redundancy on high-traffic routes.
• B. Odd-degree vertices make a closed walk that covers all edges exactly once impossible; repeating selected edges converts odd-degree vertices to even, restoring the Euler circuit condition.
• C. The carrier prefers to avoid backtracking, so skipping streets is unavoidable.
• D. Eulerian conditions apply only to directed graphs, not street networks.

Answer: (B)

An Euler circuit exists only when all vertices have even degree. With four odd-degree vertices, no closed walk can cover all edges exactly once. The solution is to add repeated traversals of certain edges to pair up odd-degree vertices — making their effective degree even. The optimal solution minimizes total repeated distance, which is a minimum-weight perfect matching on the odd-degree vertices. Without any repetition, an Euler circuit simply cannot exist.

Question 3

If a connected graph has exactly two vertices with odd degree, an Euler path must start at one of those odd-degree vertices and end at the other.

• T. True
• F. False

Answer: True

This is exact. An Euler path requires visiting every edge exactly once without backtracking to the start. A vertex 'uses up' two edges per internal visit (one in, one out), so it needs even degree to be traversable without getting stuck. The two odd-degree vertices must be endpoints: one is left first (degree contributes one unmatched outgoing edge) and one is arrived at last (one unmatched incoming edge). Starting or ending at any other vertex would violate the degree parity.

Question 4

The Königsberg bridge problem has no Euler circuit because the graph is disconnected.

• T. True
• F. False

Answer: False

The Königsberg graph is connected — all landmasses are reachable from each other via bridges. The reason no Euler circuit (or even Euler path) exists is that the graph has *four* odd-degree vertices. An Euler circuit requires all even-degree vertices; an Euler path allows exactly two. With four odd-degree vertices, neither condition is met. Euler's 1736 proof identified degree parity — not connectivity — as the decisive structural property.

Question 5

Why does satisfying the degree-parity condition guarantee the existence of an Euler circuit in a connected graph, rather than merely being a necessary condition for it?

Model answer: The degree condition is both necessary and sufficient. If every vertex has even degree in a connected graph, Hierholzer's algorithm can always construct an Euler circuit: start anywhere, follow any available edge, and continue until returning to the start. Because every vertex has even degree, you can never get trapped at an intermediate vertex — every entry into a vertex has a corresponding exit. If unvisited edges remain, splice in a new subcircuit starting from the nearest vertex with unvisited edges. The algorithm terminates with all edges visited exactly once.

The key is that even degree prevents 'getting stuck': since each visit to a vertex uses one edge in and one edge out, a vertex with even degree always has a way out whenever you enter it. The only exception is the starting vertex, which you exit first and return to last — but that's exactly the definition of a circuit. The sufficiency proof is constructive, which is why we know the condition isn't just necessary — it actively enables the construction.