How does an Eulerian cycle differ from an Eulerian trail?

Both traversals use every edge exactly once, but a cycle must return to its starting vertex while a trail does not. This difference comes from endpoint parity: a cycle has no unmatched endpoints, while a trail has two. So the odd-degree count determines which structure is possible.

What is the key distinction between a path and a trail in graph theory?

A path forbids repeating vertices, but a trail only forbids repeating edges. Eulerian traversals are defined as trails because they focus on edge coverage, not unique vertex visits. That is why Eulerian routes may revisit vertices while still being valid.

How is Eulerian classification different from Hamiltonian classification?

Eulerian classification is controlled mainly by edge usage and degree parity conditions. Hamiltonian classification concerns visiting vertices exactly once and does not follow a simple parity test. So Eulerian feasibility is usually faster to test algorithmically.

What error occurs if you count a loop as degree 1 instead of degree 2?

You corrupt the odd/even parity of that vertex and may misclassify the entire graph. Because Eulerian decisions rely on the number of odd vertices, one loop miscount can flip the conclusion from Eulerian to non-Eulerian or vice versa. Always count edge-ends, and a loop has two ends at the same vertex.

Why is it wrong to use only degree parity and ignore connectivity?

Parity is necessary but not sufficient for a single continuous edge-once traversal. If the graph has disconnected edge-containing components, no one trail can cover all edges. Connectivity must therefore be checked alongside odd-vertex counts.

What goes wrong if a semi-Eulerian trail starts at an even-degree vertex?

A semi-Eulerian graph requires exactly two odd vertices, and these must be the start and end points of the trail. Starting at an even vertex creates endpoint parity mismatch and usually leads to getting stuck or finishing at the wrong place. Correct endpoint selection is structurally forced, not optional.

What is the degree (valency) of a vertex?

The degree is the number of incident edge-ends at that vertex. It measures how many edge connections must be accounted for when traversing the graph. Loops contribute 2 because both ends touch the same vertex.

State Euler's handshaking lemma for an undirected graph.

The lemma states that the sum of all vertex degrees equals twice the number of edges. This works because each edge contributes one degree to each endpoint. A direct consequence is that odd-degree vertices always occur in an even number.

What are the degree conditions for Eulerian and semi-Eulerian graphs?

An Eulerian graph has zero odd-degree vertices, and a semi-Eulerian graph has exactly two odd-degree vertices. These conditions follow from edge pairing at internal visits during an edge-once traversal. Connectivity is also required for a valid single traversal over all edges.

Why can an Eulerian cycle revisit vertices but still be valid?

Eulerian validity is about not repeating edges, not about visiting each vertex once. A high-degree vertex may need multiple visits to access different unused incident edges. As long as each edge is used exactly once, repeated vertices are acceptable.

Library Podcasts

Courses

Referral & Rewards

Revision Notes

International A-Level

Pearson Edexcel

Maths

Decision 1

Algorithms & Graph Theory

Eulerian Graphs

Summary

Eulerian graph theory studies when a graph can be traversed edge-by-edge without repetition, either returning to the start (Eulerian cycle) or ending elsewhere (Eulerian trail). The core insight is that edge-usage constraints translate into vertex-degree parity rules, making classification fast and highly testable. This topic matters because it turns practical routing questions into clear structural checks based on connectivity and odd/even degrees.

1. Definition & Core Concepts

Fundamental objects

Degree (valency) counts how many edge-ends meet a vertex, so it measures local connectivity rather than global reachability. A loop contributes 2 to degree because both ends of that edge are incident to the same vertex, which is crucial for correct parity checks. This matters whenever you classify a graph as Eulerian or semi-Eulerian.
Eulerian trail uses every edge exactly once, while allowing repeated vertices if necessary. Eulerian cycle (circuit) also uses every edge exactly once but must end at its starting vertex. These are edge-focused ideas, so they differ from vertex-visit conditions used in other graph topics.

What the graph type means

An Eulerian graph contains at least one Eulerian cycle, so a complete closed edge traversal is possible. A semi-Eulerian graph contains an Eulerian trail but not an Eulerian cycle, so traversal is open-ended between two distinct vertices. This distinction is the foundation for method selection in exam questions and network design tasks.

2. Underlying Principles

3. Methods & Techniques

A graph with degrees and odd-vertex highlights, showing how parity determines Eulerian cycle versus semi-Eulerian trail.

4. Key Distinctions

Similar terms that are often confused

The differences are structural, not just wording differences, so you should classify by what must be used exactly once. In Eulerian settings, edges are the resource that cannot be repeated, while vertex revisits can be allowed. This single distinction prevents many classification errors.

Feature	Eulerian Cycle	Eulerian Trail
Uses every edge exactly once	Yes	Yes
Start and end vertex	Same	Different
Odd-degree vertices required	0	Exactly 2
Graph label	Eulerian	Semi-Eulerian

Path vs trail is another key contrast: a path forbids repeated vertices, but a trail only forbids repeated edges. Eulerian traversals are trails by design, so repeated vertices are acceptable when edge uniqueness is preserved.

5. Exam Strategy & Tips

6. Common Pitfalls & Misconceptions

7. Connections & Extensions

Eulerian Graphs

Summary

1. Definition & Core Concepts

Fundamental objects

Degree (valency) counts how many edge-ends meet a vertex, so it measures local connectivity rather than global reachability. A loop contributes 2 to degree because both ends of that edge are incident to the same vertex, which is crucial for correct parity checks. This matters whenever you classify a graph as Eulerian or semi-Eulerian.
Eulerian trail uses every edge exactly once, while allowing repeated vertices if necessary. Eulerian cycle (circuit) also uses every edge exactly once but must end at its starting vertex. These are edge-focused ideas, so they differ from vertex-visit conditions used in other graph topics.

What the graph type means

An Eulerian graph contains at least one Eulerian cycle, so a complete closed edge traversal is possible. A semi-Eulerian graph contains an Eulerian trail but not an Eulerian cycle, so traversal is open-ended between two distinct vertices. This distinction is the foundation for method selection in exam questions and network design tasks.

2. Underlying Principles

Degree-sum structure

The core counting law is Euler's handshaking lemma: each edge contributes exactly 2 to the total degree count because it has two endpoints. Therefore the global identity is:

$\sum_{v \in V} \deg(v) = 2|E|$

This immediately implies the number of odd-degree vertices must be even, which is the parity backbone of Eulerian tests.

Why parity controls traversability

In an edge-once traversal, each time you arrive at an internal vertex you must also leave it on a different unused edge, creating degree usage in pairs. That pairing forces internal vertices to consume an even number of incident edges, so odd degrees can only occur at unmatched endpoints of an open trail. As a result, 0 odd vertices corresponds to a closed Eulerian cycle, while exactly 2 odd vertices corresponds to an open Eulerian trail.