Bus Route Redesign
A regional town has five stops A, B, C, D, E. A proposed bus network is described by a matrix where entry (i, j) = 1 if there is a direct route between stops i and j (in either direction), and 0 otherwise. The rows and columns are ordered A, B, C, D, E. The matrix is:\n\n[0 1 1 0 0]\n[1 0 1 1 0]\n[1 1 0 0 1]\n[0 1 0 0 1]\n[0 0 1 1 0]\n\nThe council wants every stop reachable from every other stop, and wants to know the minimum number of direct routes needed so that all stops are connected (a spanning tree), and whether the current network already achieves full connectivity.
1. Determine whether every stop is reachable from every other stop in the current network. Show your reasoning using the matrix or an equivalent reachability argument.
Read the worked answer
The matrix is symmetric, so the network is undirected. Count direct links: A–B, A–C, B–C, B–D, C–E, D–E. That is 6 edges.\n\nTrace paths from A: A connects to B and C. B connects to C and D. C connects to E. So from A we can reach B, C, D (via B), and E (via C).\n\nCheck each pair: A–D via B; A–E via C; B–E via C; C–D via B; D–E directly. Every pair has a path, so the network is connected.\n\nMatrix check: A² counts walks of length 2. Entry (A,D) of A² = (row A)·(column D) = 0×0 + 1×1 + 1×0 + 0×0 + 0×1 = 1, confirming a 2-step walk A–B–D. Similarly (A,E) of A² = 0×0 + 1×0 + 1×1 + 0×1 + 0×0 = 1, confirming A–C–E. Since all off-diagonal reachability can be confirmed within 2 steps, the network is fully connected.
2. The council wants to reduce the network to a spanning tree with the minimum number of routes. Determine that minimum number and give one valid spanning tree. Explain why no spanning tree can have fewer edges.
Read the worked answer
A spanning tree on 5 vertices has exactly n − 1 = 4 edges.\n\nWhy fewer is impossible: with 3 or fewer edges on 5 vertices, at most 4 vertices can be touched by edges (each edge touches 2 vertices, and a connected graph on 5 vertices needs at least 4 edges because a connected graph with n vertices has at least n − 1 edges). More formally, any connected graph on n vertices has at least n − 1 edges, since each edge can reduce the number of connected components by at most 1 and we start with n components.\n\nWhy more is unnecessary: the current graph has 6 edges and contains cycles (A–B–C–A is a triangle; B–D–E–C–B is a 4-cycle). Removing one edge from each cycle while keeping connectivity yields a spanning tree.\n\nOne valid spanning tree: keep A–B, B–C, B–D, C–E (4 edges). Check connectivity: A–B, B–C, B–D, C–E reaches all of A, B, C, D, E. No cycle: edges form a tree rooted at B with branches to A, C, D and C extending to E. This uses 4 routes, the minimum.
3. Suppose the council must keep the direct route C–E for political reasons. Does a spanning tree containing C–E still exist with 4 edges? Give one and explain the constraint this imposes.
Read the worked answer
Yes. A spanning tree must contain C–E and still have 4 edges total.\n\nExample: C–E, A–C, B–C, B–D. Check: C–E connects E; A–C connects A; B–C connects B; B–D connects D. All five vertices connected with 4 edges and no cycle.\n\nConstraint imposed: forcing C–E means E is reached only through C (in this tree), so C becomes a cut vertex - removing C disconnects E from the rest. The council should recognise that keeping C–E does not by itself guarantee redundancy; redundancy requires an extra edge beyond the spanning tree (a cycle), which costs one more route.\n\nAlso note: if C–E were the only link to E, then any spanning tree must include it. Here E also links to D, so C–E is not forced by connectivity - it is a political constraint, and the council is trading flexibility for it. With C–E fixed, the remaining 3 edges must connect A, B, C, D, and there are several choices (e.g. A–B, B–C, B–D also works).