Network in Graph Theory · 5.1.3
Subgraphs and trees in networks
A subgraph is formed by keeping some or all vertices and edges of an original graph while preserving their connections. A tree is a special connected subgraph containing no closed loop, with exactly one fewer edge than vertices.
Students must recognise these features in a given graph and draw their own examples of valid subgraphs and trees.
The official learning standard (5.1.3)
“Identify and draw subgraphs and trees.”
What it means
A subgraph is formed by keeping some or all vertices and edges of an original graph while preserving their connections. A tree is a special connected subgraph containing no closed loop, with exactly one fewer edge than vertices.
Students must recognise these features in a given graph and draw their own examples of valid subgraphs and trees.
How it is examined
Paper 1 may show a diagram and ask pupils to identify whether it is a subgraph or a tree of a given graph. Paper 2 structured questions can require pupils to draw a specified subgraph, or a tree using given vertices, based on a network diagram provided in the question.
Worked example
The diagram shows a graph G with vertices P, Q, R, S and edges PQ, QR, RS, SP and PR. (a) Draw a subgraph of G with 4 vertices and 4 edges.
(b) Draw a tree that is a subgraph of G using all 4 vertices.
- A subgraph keeps some or all vertices and edges of G while preserving the same connections.
- For (a), choose edges PQ, QR, RS, SP (removing diagonal PR): this uses all 4 vertices and 4 edges, forming a 4-sided cycle.
- A tree with 4 vertices needs exactly 4 − 1 = 3 edges, and must have no closed loop.
- For (b), choose edges PQ, QR, RS (removing SP and PR): this connects all 4 vertices in a single path P–Q–R–S with 3 edges and no cycle.
Source:DSKP KSSM Mathematics Form 4 and 5 (Versi English)
Frequently asked questions
What's the difference between a subgraph and a tree?
A subgraph is any graph formed by selecting some vertices and edges from an original graph, keeping the same connections. A tree is a special type of subgraph that is connected, has no closed loop, and has exactly one fewer edge than its number of vertices.
How many edges must a tree with n vertices have?
Exactly n − 1 edges. This is a defining property of a tree: it has just enough edges to connect all n vertices without forming any closed loop, so removing even one more edge would disconnect it.
Can a tree contain all vertices of the original graph?
Yes. A tree that uses every vertex of the original graph is called a spanning tree, provided it remains connected, has no cycle, and has exactly one fewer edge than the total number of vertices in the graph.