Choosing the Test That Matches the Evidence
A graph may be described by an edge list, by facts about its paths, or by the way it behaves when edges are deleted. Each kind of information suggests a different way to test whether the graph is a tree. The practical skill is not to apply every test, but to identify which test uses the available facts without assuming anything that has not been established.
Throughout, graphs are finite and simple. We consider graphs with at least one vertex, so \(n=|V(G)|\ge 1\). A graph is connected if every pair of vertices can be joined by a path. It is acyclic if it contains no cycle. A tree is a connected acyclic graph. A path has no repeated vertices. For a graph on a fixed vertex set, a spanning subgraph has that same vertex set and a subset of the original edges.
The empty graph is excluded from the characterizations below: its order is zero, and the edge-count condition \(m=n-1\) would give a negative number of edges. Isolated vertices are allowed in graphs under consideration; they matter when deciding connectivity and counting components.
The Five Characterizations
These are different tests, not different definitions that must all be checked at once. Conditions (2) and (3) use an edge count together with one structural fact. Condition (4) uses path information. Condition (5) asks whether any edge can be removed while preserving connectivity.
Proof. First recall the edge count for a tree. We prove it by induction on its number of vertices. A one-vertex tree has zero edges, which is \(1-1\). For a tree with at least two vertices, take a longest path. An endpoint has degree one: an additional neighbor outside the path would extend it, while an additional neighbor on the path would create a cycle. Delete this endpoint and its single incident edge. The remaining graph is connected, since a path between remaining vertices cannot use a degree-one vertex as an internal vertex; it is also acyclic. By induction, the remaining graph has \(n-2\) edges, so the original has \((n-2)+1=n-1\).
We next show that a connected graph with \(n\) vertices has at least \(n-1\) edges, and if it has exactly \(n-1\), it is acyclic. Start with one reached vertex. As long as some vertex is unreached, connectedness guarantees an edge from the reached set to an unreached vertex: take a path from a reached vertex to any unreached one and consider the first edge that leaves the reached set. Record that edge and add its unreached endpoint. This records one distinct edge for each of the \(n-1\) vertices added. The recorded edges form an acyclic graph, because each new edge attaches a new vertex. Thus there are at least \(n-1\) edges in \(G\). If \(m=n-1\), the recorded edges are all the edges of \(G\), so \(G\) is acyclic. Together with the tree edge count just proved, this establishes the equivalence of (1) and (2).
For (3), let \(c\) be the number of connected components of an acyclic graph, counting isolated vertices as components. Each component is itself a tree, so a component with \(k\) vertices has \(k-1\) edges by the edge count above. Summing over all components gives
Consequently, if the graph is acyclic and \(m=n-1\), then \(n-c=n-1\), so \(c=1\) and the graph is connected. Conversely, a connected acyclic graph has \(m=n-1\). This proves the equivalence of (1) and (3).
For (4), a connected acyclic graph has at least one path between each pair of distinct vertices by connectedness. It has at most one: if two distinct paths joined the same pair, follow them from one endpoint until they first diverge, then continue until they next meet. The two different segments between those meeting vertices form a cycle, contradicting acyclicity. In the other direction, if every distinct pair has exactly one path, the graph is connected by the existence of those paths. It has no cycle, because two vertices on a cycle can be joined by its two different arcs. For a one-vertex graph, the pair condition is vacuous, and the graph is connected and acyclic, as required.
Finally, suppose \(G\) is connected. It has no proper connected spanning subgraph exactly when deleting any single edge disconnects it. Indeed, if a proper connected spanning subgraph omits an edge \(e\), then \(G-e\), which still contains that subgraph, is connected. Conversely, if \(G-e\) is connected, it is a proper connected spanning subgraph. If \(G\) contains a cycle, deleting one edge of that cycle leaves the graph connected: any route that used the deleted edge can use the rest of the cycle instead. Conversely, if deleting an edge leaves a connected graph, a path joining that edge’s endpoints without using the edge, together with the edge, contains a cycle. Thus every edge deletion disconnects \(G\) exactly when \(G\) is acyclic. This proves the equivalence of (1) and (5), including the one-vertex case, where there are no edges to delete. \(\square\)
Match the Test to the Information
| Information given | Test to use | What must still be checked |
|---|---|---|
| Connectedness and edge count | Connected with \(m=n-1\) | Both facts, using the same graph |
| Acyclicity and edge count | Acyclic with \(m=n-1\) | Count all vertices, including isolated ones |
| Paths between vertex pairs | Exactly one path for each distinct pair | Existence as well as uniqueness |
| Connectivity after edge deletions | Connected and edge-minimal | Every edge deletion must disconnect |
| Edge count alone | No tree test yet | Establish an additional condition |
For example, if a problem explicitly gives connectedness and \(m=n-1\), do not separately search for cycles or enumerate paths. If it gives an acyclic graph and the count, the component formula proves connectedness. But if it supplies only \(m=n-1\), neither connectedness nor acyclicity follows without more information.
Worked Example: Connectedness and an Edge Count
Let \(G\) have \(V(G)=\{1,2,3,4,5,6\}\) and \(E(G)=\{12,13,24,25,36\}\). The graph is stated to be connected; decide whether it is a tree using the shortest test.
There are six vertices, so \(n=6\). The edge list contains five distinct edges, so \(m=5\), and \(n-1=6-1=5\). Thus \(m=n-1\). Since connectedness is given, condition (2) applies, and \(G\) is a tree.
Check: Starting at vertex \(1\), the edges reach \(2\) and \(3\); from \(2\) they reach \(4\) and \(5\), and from \(3\) they reach \(6\). Hence all six vertices are reached. Also, the degrees are \(2,3,2,1,1,1\), whose sum is \(10\); counting the five listed edges at their two endpoints gives \(2\cdot5=10\). The edge count and connectivity used in the test are consistent.
Worked Example: Acyclicity and an Edge Count
Let \(G\) have \(V(G)=\{1,2,3,4,5\}\) and \(E(G)=\{12,13,14,45\}\). Suppose it is known to be acyclic. Decide whether it is a tree without separately using connectedness as input.
The graph has \(n=5\) vertices and \(m=4\) edges, so \(m=4=5-1=n-1\). The acyclic edge-count condition applies, and therefore \(G\) is connected and is a tree.
Check: The degree-one vertices \(2\) and \(3\) cannot lie on a cycle. After excluding them, the only remaining edges are \(14\) and \(45\), which do not form a cycle. Thus the stated acyclicity is also verified directly. The vertices are all connected through \(1\): vertices \(2,3,4\) are adjacent to \(1\), and vertex \(5\) is reached by \(1,4,5\). This direct check agrees with the conclusion from the criterion.
Worked Example: Unique Paths in a Star
Let \(G\) have \(V(G)=\{a,b,c,d,e\}\) and \(E(G)=\{ab,ac,ad,ae\}\). Use path information to recognize the graph as a tree.
Each of \(b,c,d,e\) has degree one, and each is adjacent only to \(a\). From \(a\) to any of these four vertices, the only path is the single edge joining them. Between any two distinct vertices among \(b,c,d,e\), the only possible path is through \(a\); for instance, the path from \(b\) to \(c\) is \(b,a,c\). The same reasoning applies to every such pair, because neither endpoint can be an internal vertex of a path. Thus every pair of distinct vertices has exactly one path, and condition (4) shows that \(G\) is a tree.
Check: There are five vertices and four listed edges, so \(n-1=5-1=4=m\). Every vertex is connected to \(a\), so the graph is connected. These independent checks also verify the connected-and-\((n-1)\)-edges test.
Worked Example: Testing Minimal Connectivity
Let \(G\) have \(V(G)=\{1,2,3,4\}\) and \(E(G)=\{12,23,34\}\). Suppose the available information is that \(G\) is connected and we can test whether deleting each edge preserves connectivity.
The graph is connected: its edges form the route \(1,2,3,4\). Delete \(12\); vertex \(1\) is then isolated. Delete \(23\); the remaining edges split the vertices into \(\{1,2\}\) and \(\{3,4\}\). Delete \(34\); vertex \(4\) is then isolated. In every case the resulting graph is disconnected, so no edge can be removed while keeping the graph connected. Condition (5) applies, and \(G\) is a tree.
Check: The graph has \(n=4\) vertices and \(m=3\) edges, with \(n-1=4-1=3\). This independent edge-count test confirms the conclusion. Each deletion check matters: showing that one edge disconnects the graph would not establish minimality.
Common Pitfall: The Edge Count Alone
A frequent mistake is to treat \(m=n-1\) as a complete tree test. The theorem requires a second condition: either connectedness or acyclicity. For a concrete counterexample, let \(H\) have \(V(H)=\{1,2,3,4,5\}\) and \(E(H)=\{12,23,13,45\}\). Here \(n=5\) and \(m=4\), so \(m=n-1=5-1=4\), but the triangle on \(\{1,2,3\}\) and the edge \(45\) are separate components. Thus \(H\) is disconnected and contains a cycle; it is not a tree.
The correction is to state the missing hypothesis before applying a characterization. If connectedness is known, use the connected edge-count test. If acyclicity is known, use the acyclic edge-count test. If neither is known, the count does not settle the question. Likewise, unique-path information must include existence, and minimal connectivity requires checking every edge, not just one.
Check Your Understanding
For each question, identify the applicable characterization and state which hypotheses are available.
- A graph has seven vertices, six edges, and is connected. Which characterization proves it is a tree?
- An acyclic graph has eight vertices and seven edges. Why does the edge count imply connectedness?
- Why does “there is at most one path between each pair” not by itself establish that a graph is connected?
- A connected graph has an edge whose deletion leaves it connected. What does this show about whether the graph is a tree?
- Give an example of a graph with \(m=n-1\) that is not a tree, and identify the missing condition.