Why Acyclicity and the Edge Count Work Together
A graph with \(n\) vertices and \(n-1\) edges is not necessarily connected: a cycle together with an isolated vertex can have exactly that count. The key additional condition is acyclicity. In a forest, every component is itself a tree, and each tree with \(r\) vertices has \(r-1\) edges. Summing over components shows that the number of components is determined by the difference between the vertex and edge counts. In particular, \(n-1\) edges leave room for only one component.
Throughout, graphs are finite and simple. A cycle is a closed path of length at least \(3\) with no repeated vertices other than its start and end. A graph is acyclic if it contains no cycle. A component is a maximal connected subgraph; isolated vertices count as components. A tree is a connected acyclic graph, and a forest is an acyclic graph. Write \(n=|V(G)|\), \(m=|E(G)|\), and \(c\) for the number of components.
This formula is the earlier result on forest edge counts. Its component-by-component meaning is useful here: if the components have vertex counts \(n_1,\dots,n_c\), each component is a tree and has \(n_i-1\) edges. Thus \(m=\sum_{i=1}^c(n_i-1)=\sum_{i=1}^c n_i-c=n-c\). For an isolated vertex, \(n_i=1\) and its edge count is \(0\), so it fits the same calculation.
The Main Characterization
Proof. Let \(c\) be the number of components of \(G\). Since \(G\) is acyclic, it is a forest, so the forest edge-count formula gives \(m=n-c\). The hypothesis \(m=n-1\) therefore implies \(n-1=n-c\), and hence \(c=1\). A graph with one component is connected. Since \(G\) is both connected and acyclic, it is a tree by definition. This also covers \(n=1\): then \(m=0\), \(c=1\), and the single-vertex graph is a tree. \(\square\)
The restriction \(n\geq1\) is necessary for the equation \(m=n-1\) to describe a graph: when \(n=0\), it would require \(m=-1\), which is impossible because an edge count is nonnegative.
Proof. If \(G\) is acyclic and has \(n-1\) edges, the theorem shows that it is connected, so it is a tree. Conversely, if \(G\) is a tree, it is a forest with exactly one component. The forest edge-count formula gives \(m=n-c=n-1\). Thus both implications hold. \(\square\)
Worked Examples
Worked Example: A Forest with Three Components
Let \(G\) have vertex set \(V=\{1,2,3,4,5,6,7\}\) and edge set \(E=\{12,23,45,67\}\). Determine its number of components and whether it is a tree.
The edges \(12\) and \(23\) form a path on \(\{1,2,3\}\); the edge \(45\) forms a component on \(\{4,5\}\); and the edge \(67\) forms a component on \(\{6,7\}\). These vertex sets are disjoint and together contain all seven vertices. Thus \(c=3\). There is no cycle: each nontrivial component is a path with respectively \(2\), \(1\), and \(1\) edges.
Directly, \(n=7\) and \(m=4\), so the forest formula gives \(c=n-m=7-4=3\), agreeing with the component list. The graph is not a tree because it is disconnected. In particular, its edge count is not \(n-1=6\).
Check: Count the edges within the three components: \(2+1+1=4=m\). Also, their vertex counts are \(3,2,2\), and \((3-1)+(2-1)+(2-1)=2+1+1=4\).
Worked Example: Acyclicity Forces One Component
Let \(G\) have vertex set \(V=\{a,b,c,d,e,f\}\) and edge set \(E=\{ab,bc,cd,de,ef\}\). Decide whether \(G\) is a tree using the theorem.
There are \(n=6\) vertices and \(m=5\) edges, so \(m=n-1=6-1=5\). The listed edges form the path \(a,b,c,d,e,f\). A path has no cycle, so \(G\) is acyclic. The theorem therefore applies and shows that \(G\) is a tree.
Check: The graph is connected because each vertex can be reached from \(a\) by following the listed path edges. It has no cycle because every edge joins consecutive vertices in that path, and there is no edge returning from \(f\) to an earlier vertex. Thus it meets the definition of a tree directly as well.
Worked Example: Two Components from the Edge Count
Let \(G\) have vertex set \(V=\{1,2,3,4,5\}\) and edge set \(E=\{12,23,45\}\). Find its number of components without relying only on a drawing, and determine whether it is a tree.
The graph is acyclic: its nontrivial pieces are the path \(1,2,3\) and the single edge \(45\), and neither piece contains a cycle. Its counts are \(n=5\) and \(m=3\). Applying the forest formula gives \(c=n-m=5-3=2\). More explicitly, the components have vertex sets \(\{1,2,3\}\) and \(\{4,5\}\).
The graph is not a tree because it has two components. The theorem does not apply: \(n-1=5-1=4\), whereas this graph has only \(3\) edges.
Check: The first component has \(3-1=2\) edges, namely \(12\) and \(23\); the second has \(2-1=1\) edge, namely \(45\). Thus the total is \(2+1=3=m\), and the component count is \(2\).
Why the Acyclicity Hypothesis Matters
The equation \(m=n-1\), by itself, does not guarantee connectedness. The proof uses acyclicity to apply the forest formula. Without it, cycles can use extra edges inside a component while other vertices or components remain disconnected.
For a concrete counterexample, let \(H\) have \(V(H)=\{1,2,3,4\}\) and \(E(H)=\{12,23,31\}\). Vertices \(1,2,3\) form a triangle and vertex \(4\) is isolated. The graph has \(n=4\) and \(m=3=n-1\), but it has two components and is not a tree. It is not acyclic, so there is no contradiction with the theorem.
A common mistake is to apply \(c=n-m\) to this graph and conclude that it has \(c=4-3=1\) component. That calculation is invalid: the formula holds for forests, not for every graph. The correct count here is two components, found from the edge list: one component on \(\{1,2,3\}\) and one on \(\{4\}\).
For a forest, the formula can also be read as \(m=n-c\). Every extra component reduces the edge count by one from the tree count \(n-1\). Thus if a forest has \(c=2\), it has \(n-2\) edges; if it has \(c=3\), it has \(n-3\) edges. The theorem is the case \(c=1\), expressed in terms of the edge count.
| Graph condition | What follows |
|---|---|
| Acyclic, with \(c\) components | \(m=n-c\) |
| Acyclic, with \(n-1\) edges and \(n\geq1\) | \(c=1\), so the graph is a tree |
| Has \(n-1\) edges, with no acyclicity assumption | Not enough information to conclude connectedness |
| Tree on \(n\geq1\) vertices | Exactly \(n-1\) edges |
When checking a proposed tree, the edge count is therefore a useful test only in combination with an acyclicity check (or another independently established condition). Counting \(n-1\) edges is not a substitute for verifying the hypothesis that allows the forest formula to be used.
Check Your Understanding
For each question, keep track of whether acyclicity has been established before using the forest edge-count formula.
- A forest has \(9\) vertices and \(6\) edges. How many components does it have?
- Explain why an acyclic graph with \(8\) vertices and \(7\) edges must be connected.
- Give a graph with \(5\) vertices and \(4\) edges that is not a tree, and identify which hypothesis of the theorem fails.
- How many edges does a forest with \(n\geq1\) vertices and \(4\) components have?
- Why does the theorem include the single-vertex graph, and what are its values of \(n\), \(m\), and \(c\)?