What Makes a Graph a Tree?
Trees are basic models for structures that are connected without containing a closed loop: examples include a route network with no circular route and a hierarchy represented by undirected links. The definition has two separate requirements. A graph must be connected, so its vertices are joined to one another, and it must be acyclic, so it contains no cycle. Checking only one requirement is not enough.
Throughout, graphs are finite and simple, so they are undirected and have no loops or multiple edges. A graph is written \(G=(V,E)\), where \(V\) is its vertex set and \(E\) its edge set. Its order is \(n=|V|\), and its size is \(m=|E|\). A path is a sequence of distinct vertices in which consecutive vertices are joined by an edge. A cycle is a sequence \(v_0,v_1,\ldots,v_{\ell-1},v_0\), where \(\ell\ge 3\), the first \(\ell\) vertices are distinct, and consecutive vertices (including \(v_{\ell-1}\) and \(v_0\)) are adjacent.
The condition “has at least one vertex” matters. For a one-vertex graph, there are no two distinct vertices to check, so the path condition is satisfied; the graph is connected. For the graph with no vertices, the explicit nonemptiness condition fails, so that graph is not connected. Both graphs have no cycles, but only the one-vertex graph is a tree.
In a finite edge list, the two parts of the tree test are different. To check connectedness, verify that every vertex can be reached from every other by a path. To check acyclicity, check that no sequence of distinct vertices returns to its starting point using edges in the list. A graph with no cycles can still have separated groups of vertices, and a connected graph can still contain a cycle.
Small Graphs and the Definition
Worked Example: The One-Vertex Graph and the Empty Graph
First let \(G_1=(V_1,E_1)\) have \(V_1=\{q\}\) and \(E_1=\varnothing\). There is one vertex and no edges. There is no pair of distinct vertices, so the requirement that every such pair be joined by a path is satisfied. Also, there cannot be a cycle: a cycle requires at least three distinct vertices. Thus \(G_1\) is connected and acyclic, hence a tree.
Now let \(G_0=(V_0,E_0)\), where \(V_0=\varnothing\) and \(E_0=\varnothing\). It has no cycles, but it has no vertices, so it fails the nonemptiness condition in the definition of connectedness. Therefore \(G_0\) is not connected and is not a tree.
Check: For \(G_1\), the order is \(1\), the size is \(0\), and the only vertex has degree \(0\); none of these facts prevents it from being a tree. For \(G_0\), the order is \(0\), so it fails connectedness before acyclicity can make it a tree.
Worked Example: A Connected Acyclic Graph
Let \(G=(V,E)\) have \(V=\{1,2,3,4\}\) and \(E=\{12,23,34\}\). We check both conditions rather than infer one from the other.
For connectedness, paths joining the six pairs of distinct vertices are: \(1,2\) for \(1\) and \(2\); \(2,3\) for \(2\) and \(3\); \(3,4\) for \(3\) and \(4\); \(1,2,3\) for \(1\) and \(3\); \(2,3,4\) for \(2\) and \(4\); and \(1,2,3,4\) for \(1\) and \(4\). Reversing any listed path gives a path in the opposite direction, so every pair is joined.
For acyclicity, the only possible edges are between consecutive labels. If a cycle existed, choose the vertex on it with the largest label. Its only possible neighbors in the graph are the preceding label and, if present, the following label. The following label is larger, so it cannot be on the cycle by the choice of the largest label. The largest-labelled vertex would then have at most one neighbor on the cycle, whereas a cycle gives each of its vertices two distinct neighbors on that cycle. This is impossible. Thus \(G\) is acyclic and is a tree.
Check: The edge list has three edges, and each of the four vertices appears in the connected chain \(1\)--\(2\)--\(3\)--\(4\). The connectivity check uses all four vertices, while the acyclicity check rules out a return to the starting vertex.
Worked Example: Connected Does Not Mean Acyclic
Let \(H=(V,E)\) have \(V=\{a,b,c,d\}\) and \(E=\{ab,bc,ca,cd\}\). The paths \(a,b\), \(b,c\), and \(c,d\) use edges in the list. The sequence \(a,b,c\) joins \(a\) to \(c\), and \(a,b,c,d\) joins \(a\) to \(d\); reversing these paths supplies paths for the corresponding reversed pairs. The remaining pair \(b,d\) is joined by \(b,c,d\). Hence every pair of vertices is joined and \(H\) is connected.
However, \(a,b,c,a\) is a cycle: its three edges are \(ab\), \(bc\), and \(ca\), and \(a,b,c\) are distinct. Therefore \(H\) is not acyclic and is not a tree.
Check: The edge \(cd\) attaches \(d\) to the part containing \(a,b,c\), so it helps make the graph connected; it does not remove the cycle \(a,b,c,a\). A connected graph is a tree only if it is also acyclic.
Worked Example: Acyclic Does Not Mean Connected
Let \(J=(V,E)\) have \(V=\{1,2,3,4\}\) and \(E=\{12,34\}\). The only paths with positive length are \(1,2\) and \(3,4\), together with their reversals. In particular, there is no path from vertex \(1\) to vertex \(3\), so \(J\) is not connected.
There is no cycle: each listed edge joins a pair that has no other edge connecting it to the other pair, and neither pair has enough edges to form a cycle. Thus \(J\) is acyclic but is not a tree.
Check: Starting from \(1\), the reachable vertices are exactly \(\{1,2\}\); vertices \(3\) and \(4\) are not reached. The edge list therefore fails the connectivity test even though it contains no cycle.
Consequences of the Definition
Proof. Let \(G\) be a tree with at least two vertices, and choose any vertex \(v\). Since \(G\) has at least two vertices, there is a vertex \(u\ne v\). By connectedness, there is a path from \(v\) to \(u\). A path from one distinct vertex to another has at least one edge, and its first edge is incident with \(v\). Therefore \(v\) is not isolated. Since \(v\) was arbitrary, no vertex of \(G\) is isolated. \(\square\)
This statement deliberately excludes the one-vertex case: its vertex is isolated, but the graph is still a tree. The distinction is not an exception to connectedness; it follows from the fact that connectedness asks for paths between distinct vertices, and there are no such pairs in a one-vertex graph.
Proof. Let the three vertices be \(a,b,c\). The only possible edges are \(ab,ac,bc\). If exactly two edges are present, they share a vertex because any two edges chosen from these three have a common endpoint. The remaining vertex is joined to that shared endpoint, and the two edges form a path through all three vertices. Thus the graph is connected. It has no cycle, since a cycle in a simple graph requires at least three edges, while this graph has exactly two. Hence it is a tree.
Conversely, suppose the graph is a tree. If it has no edges, it is not connected, since there are distinct vertices with no path between them. If it has exactly one edge, the third vertex is isolated, so it is not connected. If it has all three possible edges, then \(a,b,c,a\) is a cycle, so it is not acyclic. The only remaining possibility is that it has exactly two edges, which, as noted, share a vertex. This proves both directions. \(\square\)
Worked Example: Classifying Graphs on Three Vertices
Consider \(A=(V_A,E_A)\) with \(V_A=\{a,b,c\}\) and \(E_A=\{ab,bc\}\). The edges share \(b\), giving the path \(a,b,c\). Thus every pair is joined by a path, and there is no cycle because there are only two edges. The proposition confirms that \(A\) is a tree.
Now consider \(B=(V_B,E_B)\) with \(V_B=\{a,b,c\}\) and \(E_B=\{ab,bc,ca\}\). The three listed edges form the cycle \(a,b,c,a\). Although \(B\) is connected, it is not acyclic and is not a tree.
Check: In \(A\), the edge count is \(2\), and the shared endpoint \(b\) connects the other two vertices. In \(B\), the edge count is \(3\), and all three possible edges are present, so the displayed cycle is verified directly from the list.
A Reliable Tree Test
For a finite graph given by its vertices and edges, apply the definition as two independent checks:
- Confirm that the vertex set is nonempty. If it is empty, the graph is not connected under the convention used here and therefore is not a tree.
- Check that every pair of distinct vertices can be joined by a path. A vertex that cannot be reached from another vertex shows that the graph is not connected.
- Check that no cycle occurs in the edge list. A single cycle is enough to show that the graph is not acyclic.
- Call the graph a tree only when both connectedness and acyclicity hold.
This order is useful but not compulsory: either condition can be checked first. For instance, finding a cycle settles the question even if connectedness has not yet been checked, because a tree must be acyclic. Likewise, finding two vertices with no path between them settles the question even if no cycle has been sought, because a tree must be connected.
Common Pitfalls
Using “no cycle” as the whole definition. For \(J\) above, the edge list \(E=\{12,34\}\) contains no cycle, but vertex \(1\) cannot reach vertex \(3\). The correction is to check connectedness as well as acyclicity.
Using “connected” as the whole definition. For \(H\), the paths show that every pair can be joined, but \(a,b,c,a\) is a cycle. The correction is to check that the graph is acyclic too.
Rejecting the one-vertex graph because it has no edges. The graph \(V=\{q\}\), \(E=\varnothing\) is connected: it has at least one vertex, and there are no distinct pairs for which a path must be found. It is also acyclic, so it is a tree. By contrast, the empty graph has no vertices and is not connected under the stated definition.
Checking only one requirement in a list. A useful written check records both conclusions separately: “connected: yes/no” and “acyclic: yes/no.” The graph is a tree precisely when both answers are yes.
Check Your Understanding
For each question, use the connected-and-acyclic definition and state which condition you check.
- Is the graph with \(V=\{x\}\) and \(E=\varnothing\) a tree? Explain the role of distinct vertex pairs.
- Is the graph with \(V=\varnothing\) and \(E=\varnothing\) connected under the definition in this tutorial? Why?
- For \(V=\{1,2,3,4\}\) and \(E=\{12,23,34,41\}\), identify a cycle and decide whether the graph is a tree.
- For \(V=\{p,q,r\}\) and \(E=\{pq\}\), explain why the graph is not a tree.
- Prove directly from the definition that a graph with at least two vertices and an isolated vertex cannot be a tree.