Keeping Every Vertex, Removing Some Edges
A connected graph can contain many edges that are not needed to keep all its vertices connected. A spanning tree records one way to retain every vertex while using a connected, cycle-free selection of the graph's edges. The word spanning is essential: a tree found inside a graph is not a spanning tree if it leaves out even one vertex.
All graphs in this tutorial are finite and simple. A subgraph \(H\) of \(G\) has a vertex set \(V(H)\subseteq V(G)\) and an edge set \(E(H)\subseteq E(G)\), where every edge in \(E(H)\) has both endpoints in \(V(H)\). A graph is connected if it is nonempty and every pair of its vertices can be joined by a path. A one-vertex graph is connected. A tree is a connected graph with no cycles.
A spanning subgraph may omit edges, but it may not omit vertices. This differs from a general subgraph, which may omit both. Also, a spanning tree is not usually an induced subgraph: the induced subgraph on all vertices of \(G\) is \(G\) itself, including every edge of \(G\). A spanning tree can omit edges even when it keeps all vertices.
Throughout, the main discussion assumes \(G\) is connected and has at least one vertex. Under the convention that a tree is nonempty, the empty graph has no spanning tree. A connected graph with one vertex has a spanning tree: the subgraph with that same vertex and no edges.
How to Verify a Candidate
Suppose a candidate \(H\) is given by vertex and edge lists. First compare the vertex sets: the candidate is spanning exactly when \(V(H)=V(G)\). Then verify that every listed edge belongs to \(E(G)\) and has endpoints in \(V(H)\). Finally, test whether \(H\) is connected and has no cycle. If either of those last two properties fails, \(H\) is not a spanning tree, even if it has all the vertices.
For a connected graph on \(n\) vertices, a spanning tree has \(n-1\) edges. This is a useful check, but it does not replace checking the defining properties: the right edge count alone does not guarantee either spanning or connectedness.
Worked Example: One Spanning Tree and Two Nonexamples
Let \(G=(V,E)\), where \(V=\{1,2,3,4,5\}\) and \(E=\{12,23,34,45,51,13,35\}\). Consider three subgraphs.
First let \(T\) have vertex set \(\{1,2,3,4,5\}\) and edge set \(\{12,23,34,45\}\). Its edges form the path \(1,2,3,4,5\), so every vertex is connected to every other by a subpath, and there is no cycle. It has all five vertices of \(G\), and each of its four edges belongs to \(E\). Thus \(T\) is a spanning tree. The edge count agrees: \(5-1=4=|E(T)|\).
Next let \(H\) have vertex set \(\{1,2,3,4\}\) and edge set \(\{12,23,34\}\). These edges form a connected path with no cycle, so \(H\) is a tree subgraph of \(G\). But \(V(H)\ne V(G)\), since \(5\notin V(H)\). Therefore \(H\) is not spanning and is not a spanning tree of \(G\).
Finally let \(S\) have vertex set \(\{1,2,3,4,5\}\) and edge set \(\{12,23,34,45,51\}\). This subgraph is spanning and connected, but its edges contain the cycle \(1,2,3,4,5,1\). It is not a tree and therefore not a spanning tree. Its five edges also differ from the required tree count \(5-1=4\).
Check: The first candidate has the full vertex set, uses graph edges, and is a path on five vertices. The second is a tree but omits vertex \(5\). The third keeps every vertex but contains a cycle. Each conclusion follows from the definition, not from the edge count alone.
Connectivity and the Edge Count
The edge-count test becomes definitive when connectedness is already known. The key fact is that any connected graph on \(n\) vertices has at least \(n-1\) edges. Here is a proof that also explains why the condition concerns the number of vertices, not just the number of edges in isolation.
Proof. We use induction on \(n\). If \(n=1\), the graph has at least \(0=1-1\) edges. Now let \(n\geq2\), and assume the result for connected graphs with fewer than \(n\) vertices. Choose a vertex \(v\). The graph obtained by deleting \(v\) has \(k\geq1\) connected components, with vertex counts \(n_1,\ldots,n_k\), where \(n_1+\cdots+n_k=n-1\). Each component is connected, so by induction it has at least \(n_i-1\) edges. Since the original graph is connected, each component has at least one edge to \(v\). Edges from \(v\) to different components are distinct, and there are no edges between different components of the graph with \(v\) deleted. Consequently the original graph has at least \[ \sum_{i=1}^k(n_i-1)+k=(n-1)-k+k=n-1 \] edges. \(\square\)
Proof. Since \(H\) is spanning, it has \(n\) vertices. If \(H\) is a spanning tree, it is a tree on \(n\) vertices, which has \(n-1\) edges by the tree edge-count result established earlier. It is connected by the definition of a tree, so the stated conditions hold.
Conversely, suppose \(H\) is connected and has \(n-1\) edges. If \(H\) contained a cycle, deleting one edge of that cycle would leave \(H\) connected: the rest of the cycle still provides a route between the endpoints of the deleted edge, so any route that used that edge can be replaced by a walk using the remaining cycle edges. The resulting graph would be connected on the same \(n\) vertices but would have \(n-2\) edges. This contradicts the lemma, which requires at least \(n-1\) edges. Thus \(H\) has no cycle. It is connected, acyclic, and spanning, so it is a spanning tree. \(\square\)
In particular, when a candidate is already known to be a spanning subgraph, checking connectedness and the count \(n-1\) is enough: the theorem guarantees it has no cycle. But if connectedness has not been checked, the count alone is not enough.
Worked Example: A Spanning Tree That Is Not Induced
Let \(G=K_4\), with \(V(G)=\{1,2,3,4\}\) and \(E(G)=\{12,13,14,23,24,34\}\). Let \(T\) have \(V(T)=\{1,2,3,4\}\) and \(E(T)=\{12,23,34\}\).
The candidate includes all four vertices, and its three edges belong to \(G\). They form the path \(1,2,3,4\), which is connected and has no cycle. The count is \(4-1=3=|E(T)|\), so \(T\) is a spanning tree.
However, \(T\) is not the induced subgraph on its vertices. Since \(V(T)=V(G)\), the induced subgraph \(G[V(T)]\) is all of \(G\), with six edges, including \(13,14,\) and \(24\). Those three edges are absent from \(T\). Thus \(T\) is a spanning subgraph, but not an induced one.
Check: The path uses three edges and four vertices, and every successive pair in \(1,2,3,4\) is an edge of \(G\). The omitted edges are exactly \(13,14,24\), so \(T\) keeps all vertices without keeping all edges.
Why the Edge Count Alone Fails
The theorem requires connectedness as well as the edge count. A graph can have \(n-1\) edges and still be disconnected: edges may be concentrated in one component while other vertices lie in another component. The next example is a subgraph of a connected graph, so the failure is not due to the ambient graph being disconnected.
Worked Example: The Right Count but Two Components
Let \(G\) have vertex set \(V(G)=\{1,2,3,4,5\}\) and edge set \(E(G)=\{12,23,13,34,45\}\). The graph \(G\) is connected: vertices \(1,2,3\) are joined within the triangle, and the edges \(34\) and \(45\) link that triangle to vertices \(4\) and \(5\).
Now let \(H\) have \(V(H)=\{1,2,3,4,5\}\) and \(E(H)=\{12,23,13,45\}\). It is a spanning subgraph of \(G\), and its edge count is \(4=5-1\). But \(H\) has two components: the triangle on \(\{1,2,3\}\), and the edge on \(\{4,5\}\). There is no path in \(H\) from vertex \(1\) to vertex \(4\), because the edge \(34\) is not in \(E(H)\). Therefore \(H\) is not connected and is not a spanning tree.
Check: The four listed edges consist of three triangle edges \(12,23,13\) and one edge \(45\), so \(|E(H)|=3+1=4\). The vertex sets of the two components have sizes \(3\) and \(2\), which add to \(5\), and no listed edge joins them. The edge count matches \(n-1\), but the missing connection is decisive.
Spanning Trees and Minimal Connectivity
A connected spanning subgraph is minimal if none of its proper spanning subgraphs is connected. Here “proper” means that at least one edge has been removed; the vertex set remains the full vertex set of \(G\). For a connected graph, this minimality condition gives another way to recognize spanning trees.
Proof. Suppose first that \(H\) is a spanning tree. Removing any edge \(e=uv\) disconnects it. Otherwise, if \(H-e\) were connected, there would be a path from \(u\) to \(v\) not using \(e\). That path together with \(e\) would form a cycle in \(H\), contrary to the definition of a tree. If a proper spanning subgraph \(K\) of \(H\) is obtained by omitting one or more edges, choose one omitted edge \(e\). Then \(K\) is a subgraph of \(H-e\), which is disconnected; removing further edges cannot reconnect its components. Hence \(K\) is not connected, and \(H\) is minimal.
Conversely, suppose \(H\) is connected, spanning, and minimal among connected spanning subgraphs. If \(H\) contained a cycle, choose an edge \(e\) on that cycle. The remaining edges of the cycle provide a route between the endpoints of \(e\), so deleting \(e\) preserves connectedness. The graph \(H-e\) would then be a proper connected spanning subgraph of \(H\), contradicting minimality. Therefore \(H\) has no cycle. It is connected, spanning, and acyclic, so it is a spanning tree. \(\square\)
This characterization emphasizes that a spanning tree is a minimal way to preserve connectivity while keeping the whole vertex set. It does not say that every connected subgraph is a tree, or that any subgraph with few edges is necessarily connected.
Common Pitfall
Wrong calculation: “The candidate has \(n-1\) edges, so it must be a spanning tree.” In the previous example, \(n=5\) and \(|E(H)|=4=5-1\), but \(H\) has two components. The calculation checks only the edge count, not connectedness.
Correction: First verify that the candidate contains every vertex of the original graph. Then verify connectedness. For a spanning subgraph of a connected \(n\)-vertex graph, connectedness together with exactly \(n-1\) edges guarantees a spanning tree by the theorem. Alternatively, verify directly that the candidate is connected and has no cycles. A tree subgraph that omits vertices fails the spanning requirement, while a spanning subgraph with a cycle fails the tree requirement.
Check Your Understanding
For each question, keep the vertex-set condition separate from the edge and connectivity checks.
- Let \(G\) have \(V(G)=\{a,b,c,d\}\) and \(E(G)=\{ab,bc,cd,da,ac\}\). Is the subgraph with vertex set \(\{a,b,c\}\) and edge set \(\{ab,bc\}\) a spanning tree of \(G\)? Explain.
- Give a spanning tree of the graph \(G\) in question 1 by listing its vertices and edges, and verify its properties.
- Why does a connected spanning subgraph on \(n\) vertices with \(n-1\) edges have no cycle?
- Can a spanning tree of a graph be an induced subgraph on the full vertex set when the original graph has an edge that the tree omits? Explain.
- Explain why minimality among connected spanning subgraphs rules out cycles.