Why the Edge Count Detects Cycles
A connected graph must contain enough edges to link all its vertices. The earlier material on connected graphs establishes the lower bound: a connected graph on \(n\) vertices has at least \(n-1\) edges. The present question is what happens at equality. If a connected graph has exactly this minimum number of edges, there is no room for an edge that could be removed without breaking connectivity. An edge on a cycle can be removed while keeping the graph connected, so equality rules out cycles.
Throughout, graphs are finite and simple, and connected graphs are assumed to have at least one vertex. A graph is connected if every pair of vertices can be joined by a path. A cycle is a closed sequence of at least three edges whose vertices, apart from the repeated start and end, are distinct. A graph is acyclic if it contains no cycle. Recall that a tree is a connected acyclic graph.
The theorem uses both parts of its hypothesis: the graph must be connected, and its edge count must be exactly \(n-1\). The count alone does not imply acyclicity, and connectivity alone does not rule out cycles. We will check these distinctions in explicit examples.
Removing an Edge from a Cycle
Proof. Write \(e=uv\), and let \(C\) be a cycle containing \(e\). Removing \(e\) from \(C\) leaves a path from \(u\) to \(v\) that uses no \(e\). Take any two vertices \(x,y\) of \(G-e\). Since \(G\) is connected, there is an \(x\)-\(y\) path in \(G\). If that path does not use \(e\), it is still present in \(G-e\). If it does use \(e\), replace the traversal of \(e\) by the \(u\)-\(v\) path from \(C-e\), traversed in the required direction. The result is an \(x\)-\(y\) walk in \(G-e\). A walk between two vertices contains a path between them: whenever a vertex is repeated, delete the portion between two consecutive occurrences, repeating until no vertex is repeated. Thus \(x\) and \(y\) are joined by a path in \(G-e\). This holds for every pair, so \(G-e\) is connected. \(\square\)
The important point is that the remaining part of the cycle provides an alternate route between the endpoints of the deleted edge. Connectivity is about retaining routes between vertices, not about retaining the original routes or the same edge set.
The Equality Case
Proof. If \(n=1\), a simple graph on one vertex has no edges, since loops are excluded. It has no cycle, so the conclusion holds. Now suppose \(n\geq2\), and assume for contradiction that \(G\) contains a cycle. Choose an edge \(e\) on that cycle. By the Lemma, \(G-e\) is connected, and it has the same \(n\) vertices as \(G\). Its edge count is
But the edge lower bound says that a connected graph on \(n\) vertices has at least \(n-1\) edges. Since \(n-2<n-1\), the connected graph \(G-e\) violates that bound. This contradiction shows that \(G\) has no cycle, so it is acyclic. By the definition of a tree as a connected acyclic graph, \(G\) is a tree. \(\square\)
Each hypothesis has a specific role. The equality \(|E(G)|=n-1\) gives the exact count after deletion, while connectivity ensures that the lower bound applies to \(G-e\). The cycle supplies an edge whose deletion preserves connectivity. Without all three facts, the contradiction does not follow.
Worked Examples
Worked Example: A Connected Graph at the Lower Bound
Let \(G\) have vertex set \(V(G)=\{a,b,c,d,e\}\) and edge set \(E(G)=\{ab,bc,cd,de\}\). Decide whether the theorem applies.
There are \(n=|V(G)|=5\) vertices and \(m=|E(G)|=4\) edges. The required count is \(n-1=5-1=4\), so \(m=n-1\). The edge list gives the path \(a,b,c,d,e\), which visits every vertex; therefore any two vertices can be joined along this path, and the graph is connected. The theorem applies and says \(G\) is acyclic, hence a tree.
Check: The only listed edges join consecutive vertices in the displayed order. Starting at any vertex and following edges cannot return to an earlier vertex without reversing along an edge; there is no extra edge to close a cycle. The count also checks directly: the four listed edges are \(ab\), \(bc\), \(cd\), and \(de\), so \(m=4=n-1\).
Worked Example: A Connected Graph with a Cycle Has Too Many Edges
Let \(H\) have vertex set \(V(H)=\{1,2,3,4,5\}\) and edge set \(E(H)=\{12,23,31,34,45\}\). Is \(H\) a counterexample to the theorem?
There are \(n=5\) vertices and \(m=5\) edges, whereas \(n-1=4\). The graph is connected: vertices \(1,2,3\) are joined by the listed triangle edges, and the edges \(34\) and \(45\) link vertices \(4\) and \(5\) to that triangle. It contains the cycle \(1,2,3,1\), but it does not satisfy the theorem's edge-count hypothesis because \(5\ne4\). Thus it is not a counterexample.
We can see the proof's mechanism directly. Delete edge \(12\), which belongs to the triangle. The remaining edges are \(23,31,34,45\). The graph is still connected: \(1\) reaches \(2\) by \(1,3,2\), and the other vertices remain linked through \(3,4,5\). Its count is \(4\), which is exactly the lower bound \(n-1=4\), not less than the lower bound. The original graph had one extra edge beyond the equality case.
Check: The original edge list has five distinct edges, so \(m=5\); after deleting \(12\), four remain, so \(m'=5-1=4\). The cycle edge deletion preserves connectivity as the Lemma predicts.
Worked Example: The Edge Count Without Connectivity
Let \(F\) have vertex set \(V(F)=\{1,2,3,4,5\}\) and edge set \(E(F)=\{12,23,31,45\}\). Does the equality \(m=n-1\) imply that \(F\) is a tree?
Here \(n=5\), and the four listed edges give \(m=4=5-1=n-1\). However, the graph has two components: vertices \(1,2,3\) form a triangle, and vertices \(4,5\) form a separate edge. There is no edge between these two groups, so \(F\) is disconnected. It is not a tree, despite having \(n-1\) edges, because the theorem requires connectivity as well.
Check: The triangle contributes three edges and the separate edge contributes one, giving \(m=3+1=4\). There are five vertices, so \(n-1=5-1=4\). The cycle \(1,2,3,1\) confirms that \(F\) is not acyclic; the theorem makes no claim about this graph because it is disconnected.
Worked Example: The Single-Vertex Case
Let \(J\) have vertex set \(V(J)=\{x\}\) and edge set \(E(J)=\varnothing\). Check the theorem's condition, including the smallest allowed order.
The graph has \(n=1\) vertex and \(m=0\) edges. Thus \(n-1=1-1=0=m\). Under the usual pairwise definition of connectedness, \(J\) is connected: there are no two distinct vertices for which a connecting path needs to be checked. It has no cycle because a cycle requires at least three distinct vertices. Therefore \(J\) is acyclic and is a tree under the definition used here.
Check: The edge count is \(0=1-1\), and the edge set is empty, so no cycle can be formed. This is why the theorem states \(n\geq1\): the empty graph can involve a different convention for connectedness, and that convention is not needed here.
Common Mistakes and a Reliable Test
Mistake: using the edge count without checking connectedness. For the graph \(F\) above, a wrong calculation might say, “There are five vertices and four edges, so \(m=n-1\); therefore \(F\) is a tree.” The arithmetic is correct: \(4=5-1\). The conclusion is not, because \(F\) is disconnected and contains a triangle. The correction is to test both hypotheses before applying the theorem: count vertices and edges, then verify that every vertex lies in the same connected component.
Mistake: assuming any connected graph with a cycle contradicts the lower bound. Example \(H\) shows why the edge count matters. Removing an edge from its triangle leaves a connected graph with four edges on five vertices, which still meets the lower bound. In the theorem's equality case, the same deletion would leave only \(n-2\) edges, one fewer than a connected graph can have.
A practical test for this characterization is therefore:
- Count the vertices to obtain \(n\), then count the distinct edges to obtain \(m\).
- Check whether \(m=n-1\). If not, the theorem does not apply.
- Check connectedness. If the graph is disconnected, the theorem does not apply even if the count matches.
- If both conditions hold, conclude that the graph is acyclic and hence a tree.
This is a sufficient condition for being a tree, not a rule that the edge count alone determines the structure. The proof explains why the conditions work together: a cycle would provide an edge that can be removed without disconnecting the graph, leaving too few edges for a connected graph on the same vertices.
Check Your Understanding
For each question, state which hypothesis or proof step is relevant.
- A connected graph has six vertices and five edges. What does the theorem imply?
- A graph has six vertices and five edges, but has two components. Which hypothesis fails, and can the theorem be applied?
- Why does deleting an edge on a cycle preserve connectivity? Explain the alternate-route argument.
- A connected graph has five vertices and five edges and contains a cycle. What happens to the edge count when a cycle edge is deleted, and why is that consistent with the lower bound?
- For a graph with one vertex and no edges, verify the count and explain why it is acyclic.