Network in Graph Theory · Form 4

Network in Graph Theory: Worked Examples (KBAT)

Real planning problems where the graph idea is buried in the story: laying cable at the least total cost, re-routing a delivery when a road closes, and testing whether a proposed set of connections can exist at all. Students choose the technique themselves.

Written by the spmmath.com.my editorial team.

Worked example 1

A town council will lay fibre-optic cable so that five housing areas P, Q, R, S and T are all connected, directly or through one another, at the lowest total cost. The cost of cable (in RM'000) between areas is P–Q = 8, P–R = 5, Q–R = 6, Q–S = 9, R–S = 7, R–T = 6, S–T = 4 and P–T = 12.

Decide which cables to lay and find the least total cost.

To connect 5 areas with no wasted loop, build a spanning tree: it needs 5 − 1 = 4 cables and no cycle.
Sort the cables cheapest first: S–T = 4, P–R = 5, Q–R = 6, R–T = 6, R–S = 7, P–Q = 8, Q–S = 9, P–T = 12.
Take S–T (4), then P–R (5), no cycle yet.
Take Q–R (6): joins Q to the P, R group. Take R–T (6): joins the P-Q-R group to the S-T group, so all five are now connected.
Stop at 4 cables; the next cheapest, R–S = 7, would close a cycle, so skip it.
Least total cost = 4 + 5 + 6 + 6 = 21 (RM'000).

Worked example 2

A courier leaves the hub H and must reach customer F. The road distances (km) are H–A = 4, H–B = 9, A–B = 3, A–C = 8, B–C = 2, B–F = 10 and C–F = 3.

(a) Find the shortest route from H to F. (b) On the day, road A–B is closed for repairs.

Find the new shortest route and how much longer it is.

(a) Add up the distance on each reasonable route: H–A–C–F = 4 + 8 + 3 = 15 km.
H–B–C–F = 9 + 2 + 3 = 14 km; H–A–B–C–F = 4 + 3 + 2 + 3 = 12 km; H–A–B–F = 4 + 3 + 10 = 17 km.
The smallest total is 12 km, so the shortest route is H–A–B–C–F.
(b) With A–B closed, drop every route that uses the A–B road.
Of the routes left, H–B–C–F = 14 km and H–A–C–F = 15 km, so the new shortest is H–B–C–F = 14 km.
It is 14 − 12 = 2 km longer than the original route.

Worked example 3

A school plans covered walkways between 7 blocks. A draft says the number of walkways meeting each block should be 4, 4, 3, 3, 2, 2 and 1.

(a) Using degrees, explain why this draft cannot be built. (b) The planners change the block of degree 1 to degree 2.

Show the new plan can work and find the total number of walkways.

Treat each block as a vertex and each walkway as an edge, so the numbers given are the degrees.
The number of vertices with an odd degree must be even, because all the degrees add up to 2 × (number of edges).
(a) The odd degrees in the draft are 3, 3 and 1, three odd-degree blocks, an odd count, so no such network exists.
As a check, the sum 4 + 4 + 3 + 3 + 2 + 2 + 1 = 19 is odd, but 2 × edges must be even, it fails again.
(b) Changing the 1 to a 2 gives degrees 4, 4, 3, 3, 2, 2, 2, now only two odd-degree blocks, which is allowed.
Sum = 4 + 4 + 3 + 3 + 2 + 2 + 2 = 20, so the number of walkways = 20 ÷ 2 = 10.

Worked example 4

A resort must lay water pipes to connect 5 chalets A, B, C, D and E. The cost of a pipe between two chalets, in thousands of ringgit, is: A–B 8, A–C 5, A–E 6, B–C 9, B–D 11, C–D 15, C–E 10, D–E 7.

(a) Find the minimum total cost to connect all 5 chalets with no wasted loops, and list the pipes used. (b) A simpler plan links the chalets in one ring A–B–C–D–E–A.

How much cheaper is the minimum plan than this ring plan?

A connection with no loops is a spanning tree; for 5 chalets it needs 5 − 1 = 4 pipes.
Choose the cheapest pipes that never form a loop (smallest first): A–C 5, then A–E 6, then D–E 7, then A–B 8.
These 4 pipes connect all 5 chalets, so the minimum cost = 5 + 6 + 7 + 8 = 26 (thousand) = RM26 000.
Ring plan A–B–C–D–E–A = 8 + 9 + 15 + 7 + 6 = 45 (thousand) = RM45 000.
Saving = 45 000 − 26 000 = RM19 000.

Worked example 5

A salesman drives from town P to town T. Each road has a distance and a toll.

Petrol costs RM0.50 per km. The roads are: P–Q (40 km, toll RM6), Q–T (30 km, toll RM4), P–R (50 km, no toll), R–T (35 km, toll RM3), Q–R (10 km, toll RM1).

Find the route from P to T with the lowest total travel cost (petrol plus tolls), and state that cost.

Cost of each road = distance × RM0.50 + toll.
P–Q = 40 × 0.50 + 6 = 26; Q–T = 30 × 0.50 + 4 = 19; P–R = 50 × 0.50 + 0 = 25; R–T = 35 × 0.50 + 3 = 20.50; Q–R = 10 × 0.50 + 1 = 6.
P–Q–T = 26 + 19 = 45.00.
P–R–T = 25 + 20.50 = 45.50; P–R–Q–T = 25 + 6 + 19 = 50.00.
The lowest total cost is RM45.00 along P–Q–T.

Worked example 6

A school wants to build covered walkways so that 7 blocks form one connected network with no loops (a tree). (a) Find the least number of walkways needed.

(b) A draft plan gives these numbers of walkways at each block: A 3, B 1, C 2, D 2, E 1, F 2, G 1. Show that this matches a tree with the number of walkways from part (a).

(a) A tree with n vertices has n − 1 edges, so 7 blocks need 7 − 1 = 6 walkways.
(b) Sum of degrees = 3 + 1 + 2 + 2 + 1 + 2 + 1 = 12, and edges = 12 ÷ 2 = 6, which matches the 6 walkways of a tree.
(c) Adding one walkway raises the edge count to 6 + 1 = 7.
A connected graph with 7 vertices and 7 edges has more edges than a tree (which needs exactly 6), so it must contain a loop and cannot be a tree.

Worked example 7

A city council proposes new pedestrian bridges connecting 6 parks, with the number of bridges meeting each park given as 3, 3, 3, 2, 2 and 1. (a) Using the sum of degrees, determine whether this plan is possible.

(b) If it is possible, find the total number of bridges needed.

Sum of degrees = 3 + 3 + 3 + 2 + 2 + 1 = 14
14 is even, so this sum satisfies the requirement that the sum of degrees of any graph must be even, the plan is possible
Number of bridges = sum of degrees ÷ 2
Number of bridges = 14 ÷ 2 = 7

Worked example 8

A delivery drone flies from a warehouse W to a customer's condominium C via relay towers, because it cannot fly directly through a no-fly zone. The possible flight distances, in km, are W–P = 3, W–Q = 5, P–Q = 2, P–R = 6, Q–R = 3, Q–C = 8 and R–C = 4.

(a) Find the shortest flight route from W to C and its total distance. (b) The drone's battery allows a maximum flight distance of 11 km before it must return to base.

Determine whether the drone can complete the delivery on this route without recharging.

List possible routes and total distances:
W–Q–C = 5 + 8 = 13
W–P–R–C = 3 + 6 + 4 = 13
W–P–Q–R–C = 3 + 2 + 3 + 4 = 12
W–Q–R–C = 5 + 3 + 4 = 12
The shortest distance is 12 km, for example via W–Q–R–C
Since 12 km > 11 km, the drone cannot complete the delivery on this route without recharging

Source:DSKP KSSM Mathematics Form 4 and 5 (Versi English)

Book a Trial ClassOne-hour paid trial · Same-day reply · from RM50/hr

Frequently asked questions

What makes KBAT questions on network in graph theory different from standard practice questions?

KBAT questions place a network inside a real situation, planning delivery routes, cable connections, or event pairings, and ask you to justify a choice, such as the minimum number of edges needed to connect every vertex. You must reason from the definitions (tree, degree, connected graph) rather than apply a memorised formula, and explain your answer in words.

How do I justify an answer in words for a KBAT network question?

State the definition you are using (for example, "a tree connecting n vertices needs exactly n − 1 edges"), then apply it to the numbers in the question and state your conclusion clearly. A one- or two-sentence justification linking the rule to the given situation earns more than a bare final number.

What's a common pitfall when a KBAT network question asks for the "minimum" connections needed?

Students often draw a network that is connected but not minimal, it still contains an extra edge that could be removed without disconnecting any vertex. Before finalising your answer, check that removing any one edge from your diagram would break the connection; if not, you still have edges to cut.