Solutions — Euler Trails and Hamiltonian Paths

Fluency All vertices degree 2.

All vertices have even degree (degree 2).
→ Euler circuit exists (provided the graph is connected).
→ Euler trail (non-circuit) does NOT exist separately — the circuit IS a trail that starts and ends at the same vertex.

Fluency Degrees P=3, Q=2, R=3, S=2, T=2.

Odd-degree vertices: P (degree 3) and R (degree 3) — exactly 2.
→ Euler trail exists (no Euler circuit, since not all degrees are even).
The trail must start at P and end at R (or vice versa).

Fluency Graph: AB, BC, CA, CD, DE, EF, FD.

Degrees: deg(A) = 2, deg(B) = 2, deg(C) = 3, deg(D) = 3, deg(E) = 2, deg(F) = 2
Odd-degree vertices: C and D — exactly 2.
→ Euler trail exists, starting at C and ending at D (or vice versa).
→ No Euler circuit (not all even).

Example trail: C → A → B → C → D → E → F → D ✓

Fluency Graph: AB, BC, CD, DE, EA (5-cycle).

The graph is a pentagon (5-cycle C₅).
A Hamiltonian cycle must visit all 5 vertices exactly once and return to start.
Yes, a Hamiltonian cycle exists.
Example: A → B → C → D → E → A (this is simply the cycle itself) ✓

Understanding Graph: AB, AC, BD, BE, CD, CE, DF, EF.

(a) Degrees:
deg(A) = 2 (AB, AC), deg(B) = 3 (AB, BD, BE), deg(C) = 3 (AC, CD, CE), deg(D) = 3 (BD, CD, DF), deg(E) = 3 (BE, CE, EF), deg(F) = 2 (DF, EF)

(b) Odd-degree vertices: B, C, D, E — 4 odd-degree vertices. No Euler circuit exists.

(c) Odd-degree count = 4 > 2, so no Euler trail exists either. To create an Euler trail, you would need to add edges to make all but two vertices have even degree.

Understanding Park paths: AB, AC, BC, BD, CD, DE. Groundskeeper wants to traverse every path exactly once and return to start.

(a) Degrees: deg(A) = 2, deg(B) = 3, deg(C) = 3, deg(D) = 3, deg(E) = 1
Odd-degree vertices: B, C, D, E — 4 odd vertices.
An Euler circuit requires all even degrees. Not possible.

(b) Minimum extra paths:
To achieve an Euler circuit, we need all degrees to be even. We must pair up the 4 odd-degree vertices: (B, C), (D, E) or (B, D), (C, E) or (B, E), (C, D).
Adding one path between each pair converts those two vertices from odd to even.
Optimal pairing: add DE (making E degree 2) and BC (making B and C degree 4)... but check: DE already exists; we must add a second traversal of it. Similarly for BC.
Minimum: 2 paths must be walked twice (choose the pairing that minimises total extra distance — typically pair the closer odd vertices).

Understanding Euler circuit/trail for K₄, K₅, C₆.

(a) K₄ (4 vertices, each degree 3):
All vertices have odd degree (3). There are 4 odd-degree vertices. No Euler trail or circuit.

(b) K₅ (5 vertices, each degree 4):
All vertices have even degree (4). Euler circuit exists.

(c) C₆ (hexagon: 6 vertices, each degree 2):
All vertices have even degree (2). Euler circuit exists — simply traverse the hexagon: A→B→C→D→E→F→A.

Understanding Graph: AB, BC, CD, DE, EF, FA, AC, CE, EA.

(a) Degrees:
deg(A) = 4 (AB, FA, AC, EA), deg(B) = 2 (AB, BC), deg(C) = 4 (BC, CD, AC, CE), deg(D) = 2 (CD, DE), deg(E) = 4 (DE, EF, CE, EA), deg(F) = 2 (EF, FA)

(b) All vertices have even degree → Euler circuit exists.
Example: A → B → C → A → F → E → C → D → E → A
(There are multiple valid circuits; check that all 9 edges are used exactly once.)

(c) Hamiltonian cycle: Need to visit A, B, C, D, E, F each once and return.
Try: A → B → C → D → E → F → A ✓ (uses edges AB, BC, CD, DE, EF, FA — all valid edges)
Yes, a Hamiltonian cycle exists.

Problem Solving Network AB, AC, AD, BC, CD, CE, DE, EF, BF. Euler circuit starting at A?

Degrees:
deg(A) = 3 (AB, AC, AD), deg(B) = 3 (AB, BC, BF), deg(C) = 4 (AC, BC, CD, CE), deg(D) = 3 (AD, CD, DE), deg(E) = 3 (CE, DE, EF), deg(F) = 2 (EF, BF)

Odd-degree vertices: A, B, D, E — 4 odd vertices. No Euler circuit exists (4 odd vertices, need 0 for a circuit).

The delivery driver cannot travel every road exactly once and return to the depot. To enable a circuit, some roads must be traversed twice. The minimum extra travel is found by finding the shortest paths between paired odd-degree vertices (A–B and D–E, or A–D and B–E) and doubling those edges.

Problem Solving 8 vertices: two degree 3, six degree 2.

(a) Number of edges:
Sum of degrees = 2 × 3 + 6 × 2 = 6 + 12 = 18 = 2|E| → 9 edges

(b) Euler trail and circuit:
Odd-degree vertices: the two vertices of degree 3 — exactly 2 odd-degree vertices.
→ Euler trail exists (starting at one degree-3 vertex, ending at the other).
→ No Euler circuit (not all degrees even).

(c) Hamiltonian cycle:
A Hamiltonian cycle does not necessarily exist. The degree sequence (six 2s and two 3s) is compatible with a Hamiltonian cycle, but we cannot guarantee it without knowing the specific edge connections. For example, if the graph is shaped like two disjoint triangles joined by a bridge, a Hamiltonian cycle would be impossible. Cannot determine from degree sequence alone.