What Is a Subgraph and a Tree?

A subgraph is a graph formed using some or all of the vertices and edges of another graph. A tree is a connected graph containing no cycles.

Subgraphs

If a graph $G$ has vertex set $V(G)$ and edge set $E(G)$, a graph $H$ is a subgraph of $G$ when

$$V(H) \subseteq V(G) \quad \text{and} \quad E(H) \subseteq E(G).$$

Every edge retained in $H$ must connect the same vertices that it connects in $G$. A subgraph may omit vertices, omit edges, be disconnected, or contain cycles.

For example, suppose $G$ has vertices $\{A,B,C,D\}$ and edges $\{AB,BC,CD,DA,AC\}$. A graph with vertices and edges is a subgraph of .

Trees

A tree must satisfy two conditions simultaneously: it is connected, meaning every pair of vertices is joined by a path, and acyclic, meaning it contains no closed path returning to its starting vertex.

In the example above, $\{AB,BC\}$ forms a tree: all three vertices are connected and there is no cycle. By contrast, $\{AB,BC,AC\}$ forms a cycle and is therefore not a tree.

A common misconception is that any connected subgraph is a tree. This is false: a connected subgraph containing even one cycle is not a tree.

Exam Technique

This is HL-only content from AHL 3.14: Graph theory, applicable to GDC-active Paper 1, Paper 2, or Paper 3 questions. To justify that a graph is a tree, state both required properties: it is connected and contains no cycles; checking only that it has $n-1$ edges is insufficient without the relevant structural conditions.