Verify a Tree from an Explicit Edge List

Checking a Tree from Its Data

A graph may be given as a vertex set and an edge list, with no drawing at all. To verify that it is a tree, we need to check the graph itself rather than rely on how a sketch looks. The definition gives two separate requirements: the graph must be connected, and it must be acyclic. An edge-by-edge procedure can check both at once by tracking which vertices are connected using the edges seen so far.

Throughout, graphs are finite and simple. Thus an edge \(uv\) joins two distinct vertices, and there are no multiple edges. The vertex set must be recorded in full: a vertex absent from the edge list is still a vertex of the graph, and is isolated. A path is a sequence of distinct vertices in which consecutive vertices are adjacent. A graph is connected if every pair of its vertices is joined by a path. A cycle is a closed path of length at least three, and a graph is acyclic if it contains no cycle.

The key practical question is how an edge can affect the component structure. Start with each vertex in its own component, as no edges have yet been processed. When an edge is added, either its endpoints belong to different components, in which case those components merge, or they already belong to the same component, in which case the new edge closes a cycle. This gives a direct test for acyclicity and, at the same time, a way to track connectivity.

Why the Edge-by-Edge Check Works

Proof. Suppose first that \(u\) and \(v\) are connected in \(H\). There is a path in \(H\) from \(u\) to \(v\). That path has at least two edges, because \(uv\) is not already an edge and the graph is simple. Adding \(uv\) closes the path into a cycle.

Conversely, suppose adding \(uv\) creates a cycle. The cycle must use the new edge \(uv\), since \(H\) was acyclic. Removing \(uv\) from that cycle leaves a path in \(H\) from \(u\) to \(v\). Thus \(u\) and \(v\) were connected in \(H\). Both implications hold, so the stated test is valid. \(\square\)

Process the edges in any fixed order. At each stage, record the components formed by the processed edges. If the new edge joins different components, merge them. If its endpoints are already in the same component, record that a cycle has been found; the edge does not change the components.

Proof. We first justify the component records. After any initial segment of the edge list has been processed, two vertices belong to the same recorded component exactly when a path between them uses only processed edges. This holds before processing any edges: each vertex is a separate component, and there is no path between distinct vertices. Now process one more edge \(uv\). If \(u\) and \(v\) are in different components, the new edge joins them, and any new path between the components must use this edge. Merging the components therefore records precisely the new reachability. If \(u\) and \(v\) are already in the same component, the edge creates no connection between previously separate components. The records remain correct. This proves the claim at every stage, so the final records are the connected components of the whole graph. Since the vertex set is nonempty, the graph is connected exactly when there is one such component.

For the cycle check, the graph with no processed edges is acyclic. Suppose the edges processed so far form an acyclic graph. By the Lemma, adding the next edge creates a cycle exactly when its endpoints already lie in the same component. If they lie in different components, the enlarged graph remains acyclic; if they lie in the same component, a cycle has been found. In particular, if a cycle exists in the full graph, consider the last edge of that cycle to be processed. The other edges of the cycle already form a path between its endpoints, so the procedure records a cycle at that step. Thus the procedure records a cycle exactly when one exists. Combining the connectivity and acyclicity checks with the definition of a tree proves the result. \(\square\)

Worked Checks from Explicit Edge Lists

Common Pitfall: A Cycle Can Be Hidden in the Edge List

A list of distinct edges is not necessarily acyclic. For example, in the second worked example, none of the listed edges is repeated. That fact does not prevent the third edge from closing a cycle. After processing \(12\) and \(23\), the current component is \(\{1,2,3\}\), because those edges give the path \(1,2,3\). The next edge is \(31\), so both endpoints already belong to that component.

Wrong check: “No edge is repeated, so there is no cycle.” This checks whether the edge list has duplicates, not whether the graph has a cycle. Correction: Before adding each edge, check whether its endpoints are already connected using the earlier edges. Here \(3\) and \(1\) are already connected by \(3,2,1\), so adding \(31\) closes a cycle.

There is a second common oversight: checking whether the vertices that appear in edges are connected, while forgetting a vertex explicitly listed in \(V\). The component procedure avoids this error by starting with every vertex, including isolated ones. To verify a tree from an edge list, retain the complete vertex set, track component merges edge by edge, and require both a single final component and no recorded cycle.