Network in Graph Theory
Subgraph
A network formed from some of the vertices and edges of a larger network.
| English | Subgraph |
|---|---|
| Bahasa Melayu | Subgraf |
| 中文 | 子图 |
How it is used
From a network with vertices A, B, C, D and edges A–B, B–C, C–D, A–C, the vertices A, B, C with edges A–B and B–C form a subgraph. Every vertex and edge of a subgraph must come from the original network.
Where it shows up in SPM
Appears in the Network in Graph Theory chapter (Form 5). Paper 1 may ask which diagram is a subgraph of a given network; Paper 2 uses subgraphs when you pick out a route or a tree from within a larger network, such as the roads actually used.
Don't confuse it with
Open the chapter: Network in Graph Theory →
Frequently asked questions
Can a subgraph include all the vertices of the original network?
Yes. A subgraph may use all the vertices but only some of the edges, or only some of the vertices.
What matters is that every vertex and edge it uses already appears in the original network; it may not add any new ones.
Is the whole network a subgraph of itself?
Yes, by definition the entire network counts as a subgraph of itself, since every vertex and edge is taken from it. Usually, though, a question asks for a proper subgraph, meaning one that leaves out at least one vertex or edge.