EN
Book a Trial Class

Network in Graph Theory · Form 4

Network in Graph Theory: Worked Examples (Medium)

Puts the basics to work: reading distances off a weighted network to compare routes, counting handshakes with a complete graph, and using the tree edge rule to decide which edges to remove. For students ready to link two or three steps.

Written by the spmmath.com.my editorial team.

Worked example 1

The diagram shows roads between five towns, with distances in km: A–B = 4, A–C = 3, B–C = 1, B–D = 6, C–D = 2, C–E = 9 and D–E = 3. Find the shortest route from town A to town E and give its length.

  1. List the sensible routes from A to E and total the distances on each.
  2. A–C–E = 3 + 9 = 12 km.
  3. A–C–D–E = 3 + 2 + 3 = 8 km.
  4. A–B–C–D–E = 4 + 1 + 2 + 3 = 10 km.
  5. A–B–D–E = 4 + 6 + 3 = 13 km.
  6. The smallest total is 8 km, along A–C–D–E.

Worked example 2

Six friends at a reunion each shake hands exactly once with every other person. Modelling each person as a vertex and each handshake as an edge, find the degree of each vertex and the total number of handshakes.

  1. Each person shakes hands with the other 5, so every vertex has degree 5.
  2. This makes a complete graph on 6 vertices.
  3. Sum of degrees = 6 × 5 = 30.
  4. Number of edges = sum of degrees ÷ 2 = 30 ÷ 2 = 15.

Worked example 3

A connected network has 10 vertices and 15 edges. Explain why it cannot be a tree, and find the smallest number of edges that must be removed so that what remains is a spanning tree still connecting all 10 vertices.

  1. A tree on 10 vertices would have exactly v − 1 = 10 − 1 = 9 edges.
  2. This network has 15 edges, more than 9, so it must contain cycles and is not a tree.
  3. A spanning tree of 10 vertices needs 9 edges and must stay connected.
  4. Edges to remove = 15 − 9 = 6, taking one edge from each cycle without disconnecting the network.

Worked example 4

A graph has 7 vertices and 15 edges. Six of the vertices each have degree 4.

Find the degree of the seventh vertex.

  1. The sum of all degrees = 2 × number of edges = 2 × 15 = 30.
  2. The six known vertices contribute 6 × 4 = 24.
  3. The seventh vertex's degree = 30 − 24 = 6.

Worked example 5

The weighted network shows walking distances, in metres, between a hostel H and a library L through junctions A, B and C: H–A = 120, H–B = 100, A–C = 90, B–C = 150, C–L = 80, B–L = 260. Find the shortest distance from H to L and state the route.

  1. List the possible routes from H to L and add their distances.
  2. H–A–C–L = 120 + 90 + 80 = 290.
  3. H–B–C–L = 100 + 150 + 80 = 330.
  4. H–B–L = 100 + 260 = 360.
  5. The smallest total is 290, along H–A–C–L.

Worked example 6

A tree has 8 vertices. One vertex has degree 3 and four vertices each have degree 2.

The remaining vertices are leaves (degree 1). Find the number of leaves.

  1. A tree with 8 vertices has 8 − 1 = 7 edges, so the sum of degrees = 2 × 7 = 14.
  2. The known vertices contribute 3 + (4 × 2) = 3 + 8 = 11.
  3. The leaves together contribute 14 − 11 = 3 to the degree sum.
  4. Each leaf has degree 1, so the number of leaves = 3 ÷ 1 = 3.

Worked example 7

A computer network connects server X to client C through nodes Y, Z and router R. The transmission times, in ms, are X–Y = 5, X–R = 9, Y–R = 3, Y–Z = 8, R–Z = 2, R–C = 10 and Z–C = 4.

Find the shortest total transmission time from X to C and state the route.

  1. List possible routes and their total times:
  2. X–Y–R–C = 5 + 3 + 10 = 18
  3. X–Y–Z–C = 5 + 8 + 4 = 17
  4. X–Y–R–Z–C = 5 + 3 + 2 + 4 = 14
  5. X–R–Z–C = 9 + 2 + 4 = 15
  6. The smallest total is 14, via X–Y–R–Z–C

Worked example 8

A connected graph has 9 vertices. Six vertices each have degree 3, two vertices each have degree 4, and the remaining vertex has degree 2.

Find the total number of edges in the graph.

  1. Sum of degrees = 6(3) + 2(4) + 1(2)
  2. Sum of degrees = 18 + 8 + 2 = 28
  3. Number of edges = sum of degrees ÷ 2
  4. Number of edges = 28 ÷ 2 = 14

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

How should I approach medium-level graph theory questions on trees and subgraphs?

Medium questions usually ask you to identify or draw a tree (a connected graph with no cycles) or a subgraph within a larger network, sometimes using edge weights. Work systematically: list all vertices and edges first, then check your diagram has no closed loops for a tree, and that every edge you keep also appears in the original network for a subgraph.

What is a common pitfall when working with weighted edges in these questions?

Students sometimes add up all the edge weights in the whole network instead of only the edges belonging to the tree or subgraph asked for. Before totalling, circle exactly which edges the question wants, a total distance, a minimum connecting path, or a specific route, since including one extra edge changes the whole answer.

How much working do I need to show for a medium graph-theory question?

Show the final diagram clearly labelled, plus any total (such as sum of weights) written as a separate line, not buried inside the drawing. If you tried more than one possible tree or route, keep only your final, correct attempt clean and visible, a marker credits the labelled answer, not scattered rough sketches.

Book a Trial Class

Book a Trial Class
One-hour paid trial · Same-day replyfrom RM50/hr
Book a Trial Class