DA2 - Eulerian and Hamiltonian graphs
A route can be designed to use every edge once, or to visit every vertex once. Those are different demands. Learn to construct and justify Eulerian and semi-Eulerian trails using connectedness and vertex degrees, then decide Hamiltonian questions by explicit cycles or structural obstructions.
Trails using every edge
Can you trace two triangles sharing just one corner without lifting your pen or retracing a line, and still return to your start? A repeated vertex is allowed in this challenge; a repeated edge is not.
An Eulerian trail uses every edge of a graph exactly once. It may pass through a vertex several times. A closed Eulerian trail starts and finishes at the same vertex and is called an Eulerian circuit. An Eulerian graph has such a circuit. A semi-Eulerian graph has an open Eulerian trail with different endpoints, but no Eulerian circuit. The usual classification is for connected undirected graphs; later we will state exactly what connectivity is needed if isolated vertices are present.
An ordinary cycle does not repeat an intermediate vertex. An Eulerian circuit may repeat intermediate vertices, so it need not be a cycle in that narrower sense. Its defining condition concerns edges, not vertices.
To verify a proposed Eulerian trail, compare its consecutive edge list with the graph's complete edge list. Each edge must occur once, including any loop or multiple edge separately identified. An attractive-looking route is not enough: missing a single edge fails the condition.
Worked example 1: a closed edge traversal
Question. G has edges AB, BC, CD, DA. Give an Eulerian circuit and verify it.
Plan. Follow the square once and compare the used edges with all four supplied edges.
uses AB, BC, CD, DA, exactly once each, and returns to A.
Answer. The displayed route is an Eulerian circuit, so G is Eulerian.
Check. It has four steps, matching all four graph edges; none is repeated in reverse either.
Now add only a new vertex E and edge AE. Entering the square along that edge changes where an all-edge traversal can start and finish.
Worked example 2: a new endpoint
Question. In the graph obtained by adding AE, give an open Eulerian trail. Explain why it cannot be closed.
Plan. Use the pendant edge first, then go round the original square.
uses AE, AB, BC, CD, DA once each. A closed trail using AE would need to arrive at E and leave it, but E has only that one edge, which cannot be used twice.
Answer. The displayed route is open and uses every edge; the graph is semi-Eulerian.
Check. The five used edges match the five given edges, with endpoints E and A distinct. The leaf argument independently excludes a circuit.
A method for constructing a circuit is to follow unused edges until you return to your start, then insert another unused-edge closed trail at a vertex already visited. Repeating this splicing process uses all edges when the degree and connectivity conditions in the next part hold. Do not assume every arbitrary choice works without arranging the remaining edges: check your completed trail explicitly.
Watch out
An Eulerian route must use every edge exactly once. Repeating a vertex is allowed; repeating an edge in the opposite direction is still a repeated edge.
Verify an open route in a fresh graph.
Degree and connectivity conditions
Pairing an arrival with a departure explains why vertex degrees decide undirected Eulerian questions, provided all the edges are reachable from one another.
At an intermediate visit to a vertex, a trail uses one entering edge and one leaving edge. In a circuit this pairing includes the start, so every degree is even. In an open trail, only the distinct start and finish have one unpaired edge; their degrees are odd. A loop uses two edge ends and fits this reasoning.
Eulerian trail conditions
For a finite undirected graph with at least one edge, all vertices of nonzero degree must lie in a single connected component. Under that condition:
- a closed all-edge trail exists if and only if every vertex has even degree;
- an open all-edge trail with distinct endpoints exists if and only if exactly two vertices have odd degree. They must be its endpoints.
With more than two odd vertices, neither type exists. These conditions are not printed in the exam formula booklet.
Why are the conditions sufficient as well as necessary? When all degrees are even, a trail following unused edges cannot get stuck anywhere except its start: each arrival elsewhere leaves an unused departure. If unused edges remain, connectivity ensures some vertex of the existing closed trail leads to them. Build a further closed trail there and splice it in. Since there are finitely many edges, repeating this uses them all. With exactly two odd vertices, temporarily add an extra edge between them; all degrees become even. Construct a circuit and remove that added edge to open it into a trail between the odd vertices.
Isolated vertices have no edges to traverse, so they do not prevent the existence of an all-edge trail in the other component. However, a graph with an extra isolated vertex is not connected; state this explicitly rather than calling the whole graph connected. For the standard connected graphs of these examples, the theorem gives the usual Eulerian/semi-Eulerian classification. The one-vertex, no-edge graph admits a length-zero closed walk; it is a harmless degenerate case outside the positive-edge statement above.
[DIAGRAM: asset_name: Edge and vertex traversals; asset_slug: aqa7367-euler-hamilton; caption: Shared vertices are allowed in an Eulerian circuit but may obstruct a Hamiltonian cycle; description: Left has triangles ABC and ADE sharing only A, with edges AB BC CA AD DE EA. Right is square ABCD with diagonal AC. All five left-hand vertices and all four right-hand vertices are explicitly marked.]
Continue this lesson.
You’re previewing NovaLearn without an account. Create a free account to read the rest.
Create free account