Topic Review — Graphs and Networks — Solutions

← Graphs and Networks

This review covers graph theory definitions, Euler trails and Hamiltonian paths, shortest path (Dijkstra’s algorithm), and minimum spanning trees. Click each answer to reveal the worked solution.

Review Questions

1. A graph has vertices A, B, C, D, E with edges AB, AC, BC, BD, CE, DE. Find the degree of each vertex and verify the Handshaking Lemma. ▶ Show Answer
   deg(A) = 2, deg(B) = 3, deg(C) = 3, deg(D) = 2, deg(E) = 2
   Sum = 2+3+3+2+2 = 12 = 2 × 6 edges ✓
   Odd-degree vertices: B and C (degree 3).
2. For the graph in Question 1, does an Euler trail exist? An Euler circuit? A Hamiltonian path? ▶ Show Answer
   Odd-degree vertices: B, C — exactly 2.
   Euler trail exists (starting at B or C).
   No Euler circuit (not all degrees even).
   Hamiltonian path: try A→B→C→E→D (uses vertices A,B,C,E,D each once). Check edges: AB ✓, BC ✓, CE ✓, ED? Edge DE exists ✓. Yes, Hamiltonian path exists: A→B→C→E→D.
3. A complete graph K₅ has 5 vertices, each connected to every other. How many edges does it have? What is the degree of each vertex? Does an Euler circuit exist? ▶ Show Answer
   Edges = n(n−1)/2 = 5×4/2 = 10 edges
   Each vertex has degree 4 (connected to all other 4 vertices).
   All degrees even → Euler circuit exists.
4. Explain the difference between an Euler trail and a Hamiltonian path. Can a graph have one but not the other? ▶ Show Answer
   An Euler trail uses every edge exactly once (vertices may repeat).
   A Hamiltonian path visits every vertex exactly once (edges may be skipped).
   
   Yes, a graph can have one but not the other. For example:
   • A simple path A–B–C has a Hamiltonian path (A→B→C) but the Euler trail is the same route — in this case both coincide.
   • K₄: Hamiltonian cycle exists, but Euler circuit does not (all degrees odd = 3).
   • A graph that is a long chain with many extra edges might have an Euler trail but no Hamiltonian path.
5. A graph has 8 vertices with degrees: 2, 2, 2, 2, 3, 3, 4, 4. Does an Euler circuit exist? Does an Euler trail exist? ▶ Show Answer
   Odd-degree vertices: the two vertices with degree 3 — exactly 2.
   No Euler circuit (not all even).
   Euler trail exists, starting and ending at the two degree-3 vertices.
6. Use Dijkstra’s algorithm to find the shortest path from A to E in the graph with edges: AB=5, AC=3, BC=4, BD=7, CD=2, DE=6, CE=10. ▶ Show Answer
   Start: A=0; B→5, C→3.
   Visit C(3): B→min(5,7)=5, D→5, E→13.
   Visit B(5) and D(5) (tied): from D, E→min(13,11)=11. From B: (B→D already 5, no change).
   Visit E(11).
   
   Trace: E(11) ← D(5)+6; D(5) ← C(3)+2; C(3) ← A(0)+3.
   Shortest path: A → C → D → E = 3+2+6 = 11
7. A network of roads has edges: PQ=8, PR=4, QR=3, QS=9, RS=5, ST=7. Find the shortest path from P to T. ▶ Show Answer
   Dijkstra from P: P=0; Q→8, R→4.
   Visit R(4): Q→min(8,7)=7, S→9.
   Visit Q(7): S→min(9,16)=9 (no change).
   Visit S(9): T→16.
   Visit T(16).
   
   Trace: T(16)←S(9)+7; S(9)←R(4)+5; R(4)←P(0)+4.
   Shortest path: P → R → S → T = 4+5+7 = 16
8. What is a spanning tree? How many edges does a spanning tree of a graph with 9 vertices have? ▶ Show Answer
   A spanning tree of a connected graph is a subgraph that: contains all vertices, is connected, and has no cycles. It uses the minimum number of edges to keep the graph connected.
   
   For n = 9 vertices: spanning tree has n−1 = 8 edges.
9. Use Kruskal’s algorithm to find the MST of: AB=6, AC=2, BD=4, BC=5, CD=3, DE=8, CE=7. ▶ Show Answer
   Sorted: AC=2, CD=3, BD=4, BC=5, AB=6, CE=7, DE=8
   Add AC=2: {A,C} ✓
   Add CD=3: {A,C,D} ✓
   Add BD=4: {A,B,C,D} ✓
   Add BC=5: B and C already in same component → CYCLE, skip.
   Add AB=6: A and B already connected → skip.
   Add CE=7: {A,B,C,D,E} — all 5 connected. STOP.
   
   MST: AC=2, CD=3, BD=4, CE=7    Total = 16
10. Use Prim’s algorithm starting at vertex 1 to find the MST: 1–2=10, 1–3=6, 2–3=5, 2–4=15, 3–4=4, 4–5=8, 3–5=12. ▶ Show Answer
    Start at 1. Available: 1–2=10, 1–3=6.
    Add 1–3=6. Tree: {1,3}.
    Available: 1–2=10, 2–3=5, 3–4=4, 3–5=12.
    Add 3–4=4. Tree: {1,3,4}.
    Available: 1–2=10, 2–3=5, 3–5=12, 4–5=8, 2–4=15.
    Add 2–3=5. Tree: {1,2,3,4}.
    Available: 3–5=12, 4–5=8, 2–4=15.
    Add 4–5=8. Tree: {1,2,3,4,5}. Done.
    
    MST: 1–3=6, 3–4=4, 2–3=5, 4–5=8    Total = 23
11. State the Euler conditions for a connected graph. A graph has 6 vertices with all degrees equal to 4. What type of Euler path exists? ▶ Show Answer
    Euler conditions:
    • All vertices even degree → Euler circuit exists.
    • Exactly 2 vertices odd degree → Euler trail (not circuit) exists.
    • 4 or more vertices odd degree → no Euler trail or circuit.
    
    Graph with all degrees 4 (even): Euler circuit exists. The circuit visits every edge exactly once and returns to the starting vertex.
12. Explain the difference between a minimum spanning tree and a shortest path tree. When would you use each? ▶ Show Answer
    Minimum Spanning Tree (MST): connects all vertices with the minimum total edge weight. No specific start/end point. Used for: laying cables/pipes to connect a network as cheaply as possible (e.g. power grid, telecommunications).
    
    Shortest Path Tree: finds the minimum-weight path from one specific source vertex to all others (Dijkstra’s). Not all vertices may be included if not all are reachable by the optimal path structure. Used for: navigation (GPS routes), packet routing in computer networks, finding the fastest route between two points.
    
    Key difference: MST minimises total connection cost across all vertices. Shortest path minimises travel cost from a single source to others. The MST of a graph is not generally a shortest-path tree.
13. A postman must deliver to every street in a neighbourhood. The streets form a graph where all vertices have even degree. Explain why the postman can plan a route that starts and ends at the same location without repeating any street. ▶ Show Answer
    When all vertices have even degree, an Euler circuit exists by Euler’s theorem. An Euler circuit traverses every edge exactly once and returns to the starting vertex.
    
    In the context of the postman: each vertex represents an intersection, each edge represents a street. The even-degree condition means every time the postman enters an intersection, there is always an unused street to leave by (until the very end), allowing every street to be covered exactly once before returning home. This is the classic “Chinese Postman Problem.”
14. Find the shortest path from A to F and the minimum spanning tree for the graph: AB=3, AC=8, BC=2, BD=5, CD=4, CE=6, DF=7, EF=3. Comment on any difference between the two routes. ▶ Show Answer
    Shortest path (Dijkstra’s from A to F):
    A=0; B→3, C→8.
    Visit B(3): C→min(8,5)=5, D→8.
    Visit C(5): D→min(8,9)=8, E→11.
    Visit D(8): F→15, E→min(11,...)=11.
    Visit E(11): F→min(15,14)=14.
    Visit F(14). Path: A→B→C→E→F = 3+2+6+3 = 14.
    
    Minimum spanning tree (Kruskal’s):
    Sorted: BC=2, AB=3, EF=3, CD=4, BD=5, CE=6, DF=7, AC=8.
    Add BC=2, AB=3 (no cycle: {A,B,C}), EF=3 ({E,F}), CD=4 ({A,B,C,D}), skip BD (cycle), CE=6: connects {A,B,C,D} with {E,F} → all 6 connected. Stop.
    MST: BC=2, AB=3, EF=3, CD=4, CE=6. Total = 18.
    
    Comment: The shortest path from A to F (length 14) is not the same as any single route in the MST. The MST connects all vertices cheaply but does not guarantee the shortest A-to-F path. These are different problems solved by different algorithms.
15. A water pipe network connects 5 houses. The pipes already laid are: AE=20 m, BC=15 m, CD=10 m, DE=25 m. One more pipe must be laid to make the network connected. The remaining possible pipes and their costs are AB=18 m, AC=30 m, BD=22 m. Which pipe should be chosen to minimise total pipe length? ▶ Show Answer
    Current components: {A,E}, {B,C,D} (since BC, CD, DE is AE, and DE connects D to E which connects to A... wait: AE connects A–E; BC connects B–C; CD connects C–D; DE connects D–E. So: {A,E} and {B,C,D,E}. But DE connects D and E, so D is in {A,E} now: actually {A,D,E} via AE and DE? No: AE means A–E, DE means D–E. So E connects to both A and D. So {A,D,E} and also D connects to C via CD, so {A,C,D,E} and C connects to B via BC, so {A,B,C,D,E} — all already connected!
    
    Reinterpreting: pipes AE=20, BC=15, CD=10, DE=25 create components {A,E}, {B,C,D} (if we treat DE and AE as separate groups)... Actually DE connects D(in {B,C,D}) to E(in {A,E}), so all five are already connected.
    
    All five houses are already connected by the existing pipes. No additional pipe is needed (the network is already spanning). Total existing pipe = 20+15+10+25 = 70 m.