Questions: Eulerian Circuits and Paths

Question 1

A connected graph has five vertices with degrees 2, 4, 3, 3, 4. Which of the following is correct?

• A. It has both an Eulerian circuit and an Eulerian path
• B. It has an Eulerian path but not an Eulerian circuit, starting and ending at the two odd-degree vertices
• C. It has neither an Eulerian circuit nor an Eulerian path
• D. It has an Eulerian circuit because the majority of vertices have even degree

Answer: (B)

Two vertices have odd degree (the two vertices of degree 3); the others have even degree. Euler's theorem says: an Eulerian circuit requires ALL vertices to have even degree — that fails here. An Eulerian path requires EXACTLY TWO odd-degree vertices — that holds here. So the graph has an Eulerian path (starting at one degree-3 vertex and ending at the other) but no Eulerian circuit. Option D is a common misconception: the condition must hold for every vertex, not a majority.

Question 2

Why does an Eulerian circuit require every vertex to have even degree?

• A. Even-degree vertices are computationally easier to traverse in graph algorithms
• B. Every time a circuit passes through a vertex (neither starting nor ending there), it uses one edge to arrive and one to depart — consuming exactly two edges, requiring the degree to be even
• C. Odd-degree vertices cannot be connected to even-degree vertices in a valid graph
• D. The Hamiltonian path condition requires all degrees to be even

Answer: (B)

This is the local argument that makes Euler's theorem work. For a closed walk (circuit) traversing every edge exactly once, each interior passage through a vertex uses exactly two edges (one in, one out). The starting/ending vertex also needs a balanced count because the walk must return. If any vertex has odd degree, it cannot be perfectly balanced — the walk must either start or end there, preventing a closed circuit. This is why the condition is both necessary and sufficient.

Question 3

A graph that has an Eulerian circuit necessarily also has a Hamiltonian circuit.

• T. True
• F. False

Answer: False

Eulerian and Hamiltonian circuits are fundamentally different problems. An Eulerian circuit traverses every EDGE exactly once; a Hamiltonian circuit visits every VERTEX exactly once. A graph can have one without the other. More importantly, Eulerian circuit existence is solvable in linear time (just check the degree condition and connectivity), while Hamiltonian circuit existence is NP-complete. The surface similarity between the two problems is misleading — they have completely different theories.

Question 4

In a connected graph with exactly two odd-degree vertices, those two vertices must be the start and end points of any Eulerian path through the graph.

• T. True
• F. False

Answer: True

Euler's theorem for paths: a connected graph has an Eulerian path if and only if it has exactly two odd-degree vertices. The reason these must be the endpoints is the same local argument used for circuits: every intermediate vertex is entered and exited an equal number of times (requiring even degree). Only the starting vertex (one extra exit at the beginning) and the ending vertex (one extra entry at the end) can have odd degree. So the two odd-degree vertices are necessarily the endpoints of any Eulerian path.

Question 5

The Königsberg bridge problem asks whether you can cross all seven bridges exactly once. Explain why this is impossible, using the concept of vertex degree.

Model answer: Euler modeled the problem as a graph where the four landmasses are vertices and the seven bridges are edges. He found that all four vertices have odd degree (3 or 5 bridges each). For an Eulerian path to exist, at most two vertices can have odd degree; for a circuit, none can. With four odd-degree vertices, neither an Eulerian path nor a circuit is possible — so no such walk across all bridges exists.

This is the founding application of graph theory: translating a physical puzzle into a graph and then applying a structural condition. Euler's key insight was that the impossibility was not a matter of insufficient cleverness but a provable mathematical fact about the graph's degree sequence. The generalization — any graph with more than two odd-degree vertices has no Eulerian path — follows directly from the local balance argument.