IB Mathematics AHL 3.16 Walks, trails, paths, circuits, cycles AI HL Paper 2- Exam Style Questions- New Syllabus

(a)
It is not possible because there are more than two vertices with odd degree (specifically, four vertices have odd degrees). An Euler path exists only if exactly zero or two vertices have odd degree.

(b)
By reading the weights directly from the graph: \(a = 11, b = 18, c = 17, d = 15\).

(c)
Nearest Neighbour from \(G\):
\(G \to E\) (11), \(E \to F\) (4), \(F \to B\) (3), \(B \to D\) (5), \(D \to A\) (5), \(A \to C\) (18), \(C \to G\) (8).
Total distance \(= 11 + 4 + 3 + 5 + 5 + 18 + 8 = 54\).
Upper Bound = 54 km.

(d)
(i) MST edges: \(BF\) (3), \(EF\) (4), \(BD\) (5), \(DA\) (5), \(CD\) (15).
(ii) Total weight \(= 3 + 4 + 5 + 5 + 15 = 24\).
Weight = 24 km.

(e)
Lower Bound \(= \text{MST weight} + \text{two shortest edges from deleted vertex } G\).
Shortest edges from \(G\) are \(GE\) (11) and \(GB\) (13).
Lower Bound \(= 24 + 11 + 13 = 48\).
Lower Bound = 48 km.

(f)
An improved lower bound could be found by removing a different vertex (one at a time), calculating the corresponding lower bound for each, and selecting the maximum value obtained.

(g)
There are 7 edges in the optimal route. Since weights are to the nearest km, each edge distance \(L\) satisfies \(w – 0.5 \le L < w + 0.5\).
Using the total rounded distance of 52:
Lower bound \(= 52 – (7 \times 0.5) = 48.5\).
Lower bound = 48.5 km.