Question 11 of 12

Question 11

Question text not reproduced: the examination questions are © Engineers and Geoscientists BC. Open the official past paper (linked at the top of this page) to read the question, then follow the worked solution below.

Given. The 11-vertex graph on $\{a,\dots,k\}$ shown in the figure (edges as read from the printed figure, corrected per the check note above): $\{a,b\},\{a,d\},\{b,c\},\{b,d\},\{b,e\},\{b,f\},\{b,g\},\{c,g\},\{d,e\},\{d,h\},\{e,f\},\{e,i\},\{f,j\},\{g,k\},\{h,i\},\{i,j\},\{i,f\},\{j,k\},\{j,g\}$ (19 edges).

Find. (1) An Euler circuit of the full graph. (2) An Euler trail from $d$ to $e$ after removing edge $\{d,e\}$.

Approach. Confirm the Euler-circuit existence criterion (connected, all degrees even) before constructing one via Hierholzer's algorithm (repeatedly splice in cycles at a vertex with unused edges); after removing $\{d,e\}$, check the trail-existence criterion (exactly two odd-degree vertices, which must be the trail's endpoints) and construct the trail the same way.

1. 1) Check every vertex has even degree. Degrees: $a{=}2,\ b{=}6,\ c{=}2,\ d{=}4,\ e{=}4,\ f{=}4,\ g{=}4,\ h{=}2,\ i{=}4,\ j{=}4,\ k{=}2$ — all even, and the graph is connected, so by Euler's theorem an Euler circuit exists.
2. 1) Construct the circuit (Hierholzer's algorithm, starting at $a$). Repeatedly walk along unused edges until stuck, then splice in a further cycle at the first revisited vertex with remaining unused edges. One valid Euler circuit is: $$a\to d\to h\to i\to f\to j\to g\to k\to j\to i\to e\to f\to b\to g\to c\to b\to e\to d\to b\to a$$ This uses each of the 19 edges exactly once and returns to the start. $\boxed{\text{Euler circuit: } a\text{-}d\text{-}h\text{-}i\text{-}f\text{-}j\text{-}g\text{-}k\text{-}j\text{-}i\text{-}e\text{-}f\text{-}b\text{-}g\text{-}c\text{-}b\text{-}e\text{-}d\text{-}b\text{-}a}$
3. 2) Remove $\{d,e\}$ and recheck degrees. Removing this one edge lowers $\deg d$ and $\deg e$ from 4 to 3 each; every other vertex is unaffected. Now exactly two vertices ($d,e$) have odd degree, so by Euler's theorem the resulting subgraph has an Euler TRAIL (not circuit), and it must start and end exactly at those two odd-degree vertices — i.e. from $d$ to $e$, matching what the question asks for.
4. 2) Construct the trail (Hierholzer's algorithm from $d$). One valid Euler trail using the remaining 18 edges exactly once is: $$d\to h\to i\to f\to j\to g\to k\to j\to i\to e\to f\to b\to g\to c\to b\to d\to a\to b\to e$$ $\boxed{\text{Euler trail } d\to e:\ d\text{-}h\text{-}i\text{-}f\text{-}j\text{-}g\text{-}k\text{-}j\text{-}i\text{-}e\text{-}f\text{-}b\text{-}g\text{-}c\text{-}b\text{-}d\text{-}a\text{-}b\text{-}e}$