7.02g–7.02i - Eulerian and Hamiltonian graphs

7.02g–7.02i - Eulerian and Hamiltonian graphs

Decide when a graph can be traversed using every arc exactly once, and distinguish this from visiting every vertex exactly once. In 7.02g7.02g you will use degrees to recognise Eulerian and semi-Eulerian graphs; in 7.02h7.02h you will recognise Hamiltonian paths and cycles; in 7.02i7.02i you will apply Ore's sufficient condition for a Hamiltonian cycle.

Eulerian degree tests

A caretaker must inspect every corridor exactly once. Can the inspection finish where it starts, and would the answer be the same if the job were to visit each room exactly once? Corridors are arcs and rooms are vertices. The two instructions sound similar but impose different restrictions.

You already know

A trail repeats no arcs; a path repeats no vertices. A graph is connected when every pair of vertices can be joined by a path. The number of odd-degree vertices is even.

Imagine following a closed trail. Whenever you enter a vertex, an unused departure pairs with that arrival. Even at the starting vertex, the first departure pairs with the final arrival. If every arc is used once, all degrees must therefore be even. For an open trail, the unpaired first departure and last arrival instead give two odd-degree end vertices.

Eulerian and semi-Eulerian

A connected graph is Eulerian if it has a closed trail using every arc exactly once. It is semi-Eulerian if it has an open trail using every arc exactly once, but no such closed trail. The vertices may be revisited. These definitions are not supplied in the formula booklet.

The pairing argument gives necessary conditions. They are sufficient too: follow unused arcs until a trail stops, then splice in any remaining closed trails at visited vertices. Connectedness ensures that unused arcs cannot remain in a separate unreachable piece.

Eulerian classification

For a finite connected undirected graph:

Number of odd-degree verticesClassification0Eulerian2semi-Eulerian4,6,8,…neither\begin{array}{c|c} \text{Number of odd-degree vertices}&\text{Classification}\\ 0&\text{Eulerian}\\ 2&\text{semi-Eulerian}\\ 4,6,8,\ldots&\text{neither} \end{array}

In the semi-Eulerian case, the trail must start and finish at the two odd-degree vertices.
Not in the formula booklet: learn it.

Check connectedness before using this table. Two separate triangles have all degrees even, but no single trail can inspect both components.

Worked example 1: a closed inspection

Question. A connected graph has arcs AB,BC,CA,AD,DE,EAAB, BC, CA, AD, DE, EA. Determine whether it is Eulerian, semi-Eulerian or neither.

Plan. Count the vertex degrees and use the number that are odd.

(deg⁡A,deg⁡B,deg⁡C,deg⁡D,deg⁡E)=(4,2,2,2,2)count incident endsnumber of odd degrees=0all are even\begin{aligned} (\deg A,\deg B,\deg C,\deg D,\deg E)&=(4,2,2,2,2) && \text{count incident ends}\\ \text{number of odd degrees}&=0 && \text{all are even} \end{aligned}

Why this step? Eulerian classification concerns using arcs, so count incident arcs rather than appearances of vertices in a possible journey.

Answer. The graph is Eulerian.

Check. A,B,C,A,D,E,AA,B,C,A,D,E,A is a closed trail containing all six arcs once.

The second example changes only one connection: the arc EAEA is removed. Its two ends change parity.

Worked example 2: an open inspection

Question. Remove EAEA from the preceding graph. Determine its new classification and the required end vertices of an all-arcs trail.

Plan. Reduce the degrees of EE and AA by one, then count the odd degrees.

(deg⁡A,deg⁡B,deg⁡C,deg⁡D,deg⁡E)=(3,2,2,2,1)delete one incident end at each endodd vertices=A,Eexactly two\begin{aligned} (\deg A,\deg B,\deg C,\deg D,\deg E)&=(3,2,2,2,1) && \text{delete one incident end at each end}\\ \text{odd vertices}&=A,E && \text{exactly two} \end{aligned}

Why this step? Removing one ordinary arc flips the parity at each of its two end vertices.

Answer. The graph is semi-Eulerian, and the trail must start at AA and finish at EE, or the reverse.

Check. E,D,A,B,C,AE,D,A,B,C,A uses the remaining five arcs once.

A four-spoke star has four degree-one outer vertices. It is connected but neither Eulerian nor semi-Eulerian: an inspection must repeat at least one arc.

Watch out

Wrong: “There are two odd vertices, so start anywhere.” An open all-arcs trail must start at one odd vertex and finish at the other. Starting at an even vertex cannot use every arc exactly once.

Use degrees to classify a different graph, including its allowed end points.

Constructing an all-arcs trail

The degree test decides whether a trail exists. To exhibit one, write a consecutive list of vertices and tick off each arc as you use it. If you finish a small circuit while arcs remain, insert another circuit at a shared vertex rather than repeating an already used connection.

[DIAGRAM: asset_name: Splicing two circuits; asset_slug: h245_7_02_eulerian_splice; caption: Two triangular circuits can be joined at A into a single closed trail; description: Two triangles ABC and ADE share only vertex A. Blue arrows show A to B to C to A, and sage arrows show A to D to E to A. A lower line gives the full trail A B C A D E A and states that A is repeated but no arc is repeated.]
Two triangular circuits can be joined at A into a single closed trail

The picture is the caretaker's first case: visiting the junction AA more than once is allowed because the instruction concerns corridors. Do not impose a no-repeated-vertices rule on an Eulerian trail.

Worked example 3: splicing closed trails

Question. Construct an Eulerian trail for the graph with arcs AB,BC,CA,AD,DE,EA,AF,FG,GAAB, BC, CA, AD, DE, EA, AF, FG, GA.

Plan. Traverse each of the three triangles in turn from the shared vertex AA.

first circuit:A,B,C,Auses AB,BC,CAsecond circuit:A,D,E,Auses AD,DE,EAthird circuit:A,F,G,Auses AF,FG,GA\begin{aligned} \text{first circuit}&: A,B,C,A && \text{uses }AB,BC,CA\\ \text{second circuit}&: A,D,E,A && \text{uses }AD,DE,EA\\ \text{third circuit}&: A,F,G,A && \text{uses }AF,FG,GA \end{aligned}

Why this step? Each circuit returns to the shared vertex, so the next circuit can begin without retracing an arc.

Answer. One Eulerian trail is A,B,C,A,D,E,A,F,G,AA,B,C,A,D,E,A,F,G,A.

Check. The list has nine steps, one for each of the nine distinct arcs, and finishes at AA.

The second example changes only one feature: the final arc GAGA is deleted, so the traversal becomes open.

Worked example 4: finishing at the other odd vertex

Question. Construct an all-arcs trail after GAGA is removed from the graph in Worked example 3.

Plan. Start at odd vertex GG, follow the branch to AA, then complete the two remaining circuits.

deg⁡G=1,deg⁡A=5the odd verticesinitial steps:G,F,Ause the branch onceremaining steps:A,B,C,A,D,E,Asplice the two circuits\begin{aligned} \deg G&=1,\qquad \deg A=5 && \text{the odd vertices}\\ \text{initial steps}&:G,F,A && \text{use the branch once}\\ \text{remaining steps}&:A,B,C,A,D,E,A && \text{splice the two circuits} \end{aligned}

Why this step? Starting at the degree-one vertex uses its only arc as the initial departure, so no later return along it is needed.

Answer. G,F,A,B,C,A,D,E,AG,F,A,B,C,A,D,E,A is a suitable trail.

Check. Its eight steps use exactly the eight remaining arcs, starting at GG and finishing at AA.

Continue this lesson.

You’re previewing NovaLearn without an account. Create a free account to read the rest.

Create free account