Counterexamples to Tree Tests Based on Edge Counts

Why an Edge Count Alone Is Not Enough

For a finite tree with \(n\) vertices, the number of edges is \(n-1\). It is tempting to reverse this fact and decide that any graph with \(n-1\) edges must be a tree. That conclusion is false: the edge count records how many edges there are, but not how they are distributed among components. A graph can have a cycle in one component and an isolated vertex or another component elsewhere.

Throughout, graphs are finite and simple, and we consider graphs with \(n\ge 2\) vertices. A tree is a connected acyclic graph. A component is a maximal connected subgraph; write \(c\) for the number of components. A graph is disconnected if it has at least two components. We use the earlier forest edge-count formula: a forest on \(n\) vertices with \(c\) components has \(n-c\) edges. In particular, a tree on \(n\) vertices has \(n-1\) edges.

Key point: The condition \(|E(G)|=n-1\) is necessary for a tree, but it is not sufficient on its own. Adding either connectedness or acyclicity makes it a valid tree test.

How Disconnected Graphs Can Have \(n-1\) Edges

Let a graph have components \(G_1,\dots,G_c\), with \(n_i\) vertices and \(m_i\) edges in component \(G_i\). Since each component is connected, the earlier lower bound for connected graphs gives \(m_i\ge n_i-1\). Define the component's edge excess by \(r_i=m_i-(n_i-1)\), so \(r_i\ge0\). Summing over the components, and using \(\sum_i n_i=n\), gives

|E(G)|=\sum_{i=1}^{c}m_i =\sum_{i=1}^{c}(n_i-1+r_i) =n-c+\sum_{i=1}^{c}r_i.

Thus a disconnected graph with \(n-1\) edges must satisfy \(\sum_i r_i=c-1\). When \(c\ge2\), this sum is positive, so at least one component has positive excess. Such a component has more than \(n_i-1\) edges and therefore cannot be a tree. Since it is connected, not being a tree means it is not acyclic: it contains a cycle. This explains the counterexamples in general. The components' cycles supply extra edges, while the separation into multiple components leaves fewer edges than a connected graph on the same number of vertices would require.

Proposition: If a graph with \(n\ge2\) vertices is disconnected and has \(n-1\) edges, then at least one of its components contains a cycle.

Proof. Let \(c\ge2\) be the number of components. If every component were acyclic, the whole graph would be a forest. The forest edge-count formula would then give \(|E(G)|=n-c\le n-2\), contradicting \(|E(G)|=n-1\). Therefore the graph is not acyclic, so it contains a cycle. A cycle lies entirely within a single component, which proves the claim. \(\square\)

Worked Example: A Triangle and an Isolated Vertex

Let \(G\) have vertex set \(V=\{1,2,3,4\}\) and edge set \(E=\{12,23,31\}\). Check whether the edge count makes \(G\) a tree.

There are \(n=|V|=4\) vertices and \(m=|E|=3\) edges. Since \(n-1=4-1=3\), the graph does have \(n-1\) edges. But vertices \(1,2,3\) form a triangle: the edges \(12,23,31\) join them in a cycle. Vertex \(4\) has no incident edge, so it is an isolated component. The graph is disconnected and contains a cycle, hence is not a tree.

Check: The two components have sizes \(3\) and \(1\). The triangle component has \(3\) edges and the isolated-vertex component has \(0\), giving \(3+0=3\) edges altogether. The forest count for a forest with \(n=4\) vertices and \(c=2\) components would be \(4-2=2\), not \(3\); the extra edge is precisely what closes the triangle.

Worked Example: A Cycle Component and a Path Component

Let \(G\) have vertex set \(V=\{a,b,c,d,e,f,g\}\) and edge set \(E=\{ab,bc,cd,da,ef,fg\}\). Determine whether \(G\) is a tree, and account for its edge count component by component.

The vertices \(a,b,c,d\) form a 4-cycle, and \(e,f,g\) form a path with edges \(ef\) and \(fg\). There are no edges between these two sets, so \(G\) has \(c=2\) components. The total number of vertices is \(n=7\), and the edge list has \(m=6\) edges. Substituting gives \(n-1=7-1=6=m\), yet the graph is disconnected and cyclic. It is not a tree.

The component excesses show how the count works. For the 4-cycle, \(n_1=4\), \(m_1=4\), and \(r_1=4-(4-1)=1\). For the path, \(n_2=3\), \(m_2=2\), and \(r_2=2-(3-1)=0\). Therefore \(\sum_i r_i=1=c-1\), as required when a graph with two components has \(n-1\) edges.

Check: The degrees in the displayed edge list are \(2,2,2,2,1,2,1\), whose sum is \(12\). By the handshake lemma, the number of edges is \(12/2=6\), agreeing with the edge list and with \(n-1=6\). This independent count confirms that the failure is not an edge-counting error: it is the missing connectedness.

The Conditions That Complete the Test

Theorem: For a graph \(G\) with \(n\ge2\) vertices, the following statements are equivalent: (1) \(G\) is a tree; (2) \(G\) is connected and has \(n-1\) edges; (3) \(G\) is acyclic and has \(n-1\) edges.

Proof. If \(G\) is a tree, then it is connected and acyclic by definition. The earlier edge-count formula for trees gives \(|E(G)|=n-1\), so both (2) and (3) hold.

Suppose next that \(G\) is connected and has \(n-1\) edges. If \(G\) had a cycle, choose an edge \(e\) on that cycle. Deleting \(e\) leaves the graph connected: whenever a route used \(e\), the rest of the cycle provides an alternate route between its endpoints. The graph \(G-e\) would therefore be connected on the same \(n\) vertices, but would have \((n-1)-1=n-2\) edges. This contradicts the earlier result that a connected graph on \(n\) vertices has at least \(n-1\) edges. So \(G\) has no cycle. It is connected and acyclic, hence a tree, proving that (2) implies (1).

Finally, suppose that \(G\) is acyclic and has \(n-1\) edges. Then it is a forest. If it has \(c\) components, the forest edge-count formula gives \(n-1=n-c\), so \(c=1\). Thus \(G\) is connected as well as acyclic, and hence is a tree. This proves that (3) implies (1), completing both equivalences. \(\square\)

The theorem gives two separate valid tests. If connectedness is already known, checking \(n-1\) edges is enough. If acyclicity is already known, checking \(n-1\) edges is also enough. Without either condition, the edge count does not decide whether the graph is a tree.

Worked Example: Applying the Connectedness Test

Let \(G\) have vertex set \(V=\{1,2,3,4,5\}\) and edge set \(E=\{12,23,34,45\}\). Use the connectedness-plus-edge-count test to decide whether \(G\) is a tree.

The edge list contains \(m=4\) edges, while \(n=5\), so \(n-1=5-1=4\). The graph is connected: starting at vertex \(1\), the listed edges give a route \(1,2,3,4,5\) that reaches every vertex. The theorem now applies, because both hypotheses have been checked: \(G\) is connected and \(m=n-1\). Therefore \(G\) is a tree.

Check: The degrees are \(1,2,2,2,1\), which sum to \(8\); the handshake lemma gives \(8/2=4\) edges. Also, each edge joins consecutive vertices in the displayed order, so there is no edge that closes a cycle. This confirms the conclusion directly from the edge list.

Common Mistakes and a Reliable Procedure

Mistake: treating a necessary condition as sufficient. A wrong argument might say, “A tree on \(n\) vertices has \(n-1\) edges. This graph has \(n-1\) edges, so it is a tree.” The conclusion does not follow: the first statement says that every tree has this edge count, not that every graph with this edge count is a tree. For the graph on \(\{1,2,3,4\}\) with edges \(\{12,23,31\}\), the calculation is \(n-1=4-1=3=m\), but the triangle and isolated vertex show that it is not a tree.

The correction is to check the missing structural condition. For that graph, connectedness fails and acyclicity fails, so neither version of the valid test applies. In contrast, once connectedness is established, \(n-1\) edges force acyclicity; once acyclicity is established, \(n-1\) edges force connectedness.

For a graph given by an explicit edge list, use this sequence:

Count its vertices to obtain \(n\), and count its distinct edges to obtain \(m\).
Check whether \(m=n-1\). If not, the graph is not a tree.
If the counts agree, check connectedness or acyclicity rather than stopping at the count.
Conclude that the graph is a tree if it is connected, or if it is acyclic; otherwise the edge count alone has not certified a tree.

This order separates arithmetic from structure. A correct edge count is useful, but it becomes a tree test only alongside a condition that rules out the disconnected cyclic examples.

Check Your Understanding

For each question, distinguish the edge count from the structural condition that is also needed.

Give a graph with \(5\) vertices and \(4\) edges that is disconnected and contains a cycle. Specify its vertex set and edge set.
A forest has \(8\) vertices and \(3\) components. How many edges does it have? Explain whether it can have \(7\) edges.
Explain why a connected graph with \(n\) vertices and \(n-1\) edges cannot contain a cycle.
A graph has \(n-1\) edges and is acyclic. What does the forest edge-count formula imply about its number of components?
Identify the missing hypothesis in the claim, “Every graph with \(n-1\) edges is a tree,” and give a counterexample.