A network can remain connected despite the loss of some links. A tree is at the opposite extreme: it is connected, but every edge is indispensable. This section explains why that local property is equivalent to a global prohibition on cycles.
Definitions
Definition 1.1.1
(Walks, paths, cycles and bridges)
A finite simple undirected graph is a pair , where is finite and is a set of two-element subsets of . A walk is a sequence of vertices with consecutive vertices adjacent; a path is a walk with no repeated vertex. A path of length zero joins a vertex to itself. A graph is connected when every pair of vertices is joined by a path. A cycle is a closed walk of length at least three whose vertices are distinct except for its first and last vertices. An edge is a bridge if deleting it increases the number of connected components.
Theorem 1.1.2
(Bridge criterion)
An edge belongs to no cycle if and only if it is a bridge.
Proof
(Proof by rerouting around a cycle)
Let . If lies on a cycle, the remainder of that cycle is a path from to avoiding . Any walk using can replace each traversal of by this path; deleting repeated portions produces a path. Hence deletion of cannot separate vertices formerly connected. Conversely, if is not a bridge, and remain connected after deletion: otherwise the component containing would split, since every former path between its two sides had to use . A simple – path avoiding , together with , forms a cycle.
The distinction between a walk and a path matters: concatenating paths may repeat vertices, but a finite walk can be shortened to a path by repeatedly deleting the segment between two occurrences of the same vertex.
Theorem/proposition
Definition 1.1.3
(Tree and forest)
A tree is a connected acyclic finite simple graph with at least one vertex. A forest is an acyclic graph; its components are trees, with isolated vertices allowed.
Theorem 1.1.4
(Characterizations of trees)
For a graph on vertices, the following conditions are equivalent:
- It is a tree.
- Every pair of vertices is joined by exactly one path.
- It is connected and has edges.
- It is acyclic and has edges.
Proof
(Proof through leaves, spanning trees and the forest count)
In a tree, connectedness supplies a path. Two distinct paths with the same endpoints yield a cycle: follow them from their first divergence to their next common vertex. Thus (1) implies (2), and (2) implies (1), since a cycle gives two paths between adjacent vertices on it.
Every finite tree with at least two vertices has a leaf, a vertex of degree one. To see this, choose a longest path. Its endpoint cannot have a neighbor outside the path, or the path could be extended; nor can it have another neighbor on the path, or there would be a cycle. Remove that endpoint and its incident edge. The remaining graph is connected and acyclic: a path between remaining vertices cannot use the removed leaf internally. Induction from the one-vertex tree shows that every tree has edges, so (1) implies (3) and (4).
Every finite connected graph has a spanning tree: while there is a cycle, delete an edge on it. The bridge criterion preserves connectedness, and the finite process ends with a connected acyclic graph. Therefore a connected graph has at least edges. If it has exactly , its spanning tree already uses every edge, proving (3) implies (1). Finally, if a forest has components of sizes , the tree count gives . An acyclic graph with edges has , proving (4) implies (1).
Proof X-ray
Each arrow uses a different tool
The equivalence of (1) and (2) uses only the divergence argument: two distinct paths with common ends contain a cycle, and a cycle supplies two paths. The edge count rests on the leaf lemma, and finiteness enters there, through the choice of a longest path; the induction then removes one leaf and one edge at a time while keeping a tree.
The converses need constructions rather than counts. For (3), a spanning tree is produced by deleting cycle edges, and the bridge criterion is exactly what guarantees that no deletion disconnects; since the spanning tree has edges and the graph has no more, nothing was deleted. For (4), the count is applied component by component, , and the hypothesis forces . In both converses the edge count does work only together with the second property, connectedness in (3) and acyclicity in (4).
Neither accompanying property can be dropped from the edge-count conditions.
Counterexample mode
Only an edge count does not characterize trees
The nonempty hypothesis avoids a convention dispute: the empty graph has no components and is not called a tree here. Also, edges alone does not imply a tree. A triangle together with an isolated vertex has four vertices and three edges, but is disconnected and contains a cycle.
Worked examples
Worked example 1.1.5
(Bridges and spanning trees of a triangle with a tail)
Let and , abbreviating by . The triangle edges lie on a cycle, so none is a bridge. The edge lies on no cycle and is a bridge. Delete to obtain the path , a spanning tree with three edges. Deleting instead isolates ; this illustrates why the bridge criterion matters. A spanning tree is generally not unique: deleting from the original graph gives another one.
Exercises
Quick check
(A forest has vertices and edges. How many components does it have?)
Solution · Answer
The formula gives . Isolated vertices count as components.
Quick check
(A connected graph has vertices and edges. Show that it has exactly one cycle.)
Solution · Answer
Select a spanning tree , which has edges. The graph has exactly one edge outside . The unique – path in together with is a cycle. Every cycle must contain an edge outside , since is acyclic; it must therefore contain . Removing from such a cycle leaves a – path in , and uniqueness forces it to be the path already identified. Hence there is exactly one cycle.
Adding an edge to a tree
Theorem 1.1.6
(Adding an edge to a tree creates one cycle)
Let be a tree and let be distinct nonadjacent vertices. Adding the edge creates exactly one cycle, formed by the unique – path in together with the new edge.
Proof
(Proof by uniqueness of tree paths)
The unique path from to in , together with the new edge, is a cycle. Any cycle in the enlarged graph must use the new edge, because itself is acyclic. Removing that edge from the cycle leaves a path in from to , and the characterization of trees forces that path to be the one already found.
This observation gives a useful exchange operation. If is any edge of this cycle other than the new edge, deleting produces another spanning tree. To check connectedness, replace a traversal of with the remaining part of the cycle. The new graph has edges and is connected, so it is a tree. The operation does not say that deleting an arbitrary edge outside this cycle preserves connectedness.
Concept lensStructural
Minimally connected and maximally acyclic
A tree is exactly a minimally connected graph: connected, with every edge a bridge, since by the bridge criterion “no edge lies on a cycle” and “every edge is a bridge” say the same thing. Dually, a tree is exactly a maximally acyclic graph: acyclic, and adding any edge between nonadjacent vertices creates a cycle, by the theorem above. Conversely, a maximally acyclic graph is connected, because an edge joining two components would create no cycle.
Worked example 1.1.7
(An exchange on a path)
Start with the path and add . The unique cycle is . Delete to get the tree with edges : its unique path from to is . By contrast, if the original tree had an extra leaf joined only to , the edge would not lie on this cycle; deleting it would isolate .
Counting and construction are different questions
Common mistake
(Using the forest count before acyclicity is known)
The formula counts components of a forest, but it cannot be applied to a graph before acyclicity is established. For example two disjoint triangles have six vertices, six edges and two components, while . A cycle edge adds redundancy without changing connectivity, so an edge count alone misses the component structure.
A spanning tree can be found without testing all subsets of edges. Starting from any vertex of a connected finite graph, repeatedly add an edge with exactly one endpoint already reached and add its other endpoint. Such an edge exists until every vertex has been reached: take a path from a reached vertex to an unreached vertex and use its first edge leaving the reached set. Each step adds one vertex and one edge, and cannot create a cycle because the newly added vertex has only one edge in the constructed subgraph. The result is a spanning tree. Different choices can yield different trees; no claim of minimum total weight is made.
Worked example 1.1.8
(Two spanning trees grown from one vertex)
In a square with diagonal , begin at . Choose edges , then , then . They reach all four vertices and form a tree. Choosing instead gives a different tree. Neither choice is justified as cheapest unless edge weights and an optimization algorithm are supplied.
Further practice
Quick check
(A tree has vertices. A new edge joins two previously nonadjacent vertices. How many edges must be removed to recover a tree on the same vertices, and which edges are eligible?)
Solution · Answer
The new graph has edges, while any tree on these vertices has , so exactly one edge must be removed. The new edge or any edge on the unique cycle works: the remainder of that cycle keeps its endpoints connected. An edge outside the cycle cannot work, because it was already a bridge of the original tree and the new edge does not supply a path around it. To see the latter, deleting such an edge separates the original tree into two parts; the endpoints of the new edge remain in the same part because their original path avoided the deleted edge.
Quick check
(Prove that a tree with at least two vertices has at least two leaves.)
Solution · Answer
Choose a longest path. The argument used above for one endpoint also applies to the other. Both endpoints have degree one, and they are distinct because the tree has at least two vertices. This proof relies on finiteness: an infinite two-way path has no leaf.
Degree accounting in trees
Every edge of a finite simple graph contributes one to the degree of each endpoint, so . For a tree with , subtracting for each vertex yields
Let denote the number of leaves. Each leaf contributes , each degree-two vertex contributes zero, and every vertex of degree at least three contributes a positive integer. Thus
This strengthens the two-leaf result: a degree-four vertex forces at least four leaves. It also explains why the one-vertex tree must be excluded from this formula: its sole vertex has degree zero, not one, and contributes rather than .
Worked example 1.1.9
(Leaves forced by one vertex of degree four)
A tree has exactly one degree-four vertex and every other vertex has degree one or two. The formula gives . It does not determine how many degree-two vertices there are: subdividing any edge inserts a degree-two vertex without changing the number of leaves. The star on five vertices and the tree obtained by subdividing one of its edges both fit the description.
Quick check
(A tree has six leaves, two vertices of degree three, one vertex of degree four, and all remaining vertices have degree two. Can these degrees occur?)
Solution · Answer
The leaf formula requires , so the count is consistent. To show actual existence rather than merely a necessary condition, join the degree-four vertex to two degree-three vertices and two leaves. Attach two further leaves to each degree-three vertex. The resulting connected acyclic graph has the stated degrees; degree-two vertices can be inserted by subdividing edges. Consistency of a numerical identity alone would not have proved existence.
Common mistakes
Common mistake
(Assuming uniqueness of paths while proving acyclicity)
When proving a statement about a tree, first identify which of its two defining properties is doing the work. Connectedness gives a path, but says nothing by itself about its uniqueness: a triangle has two paths between adjacent vertices. Acyclicity gives uniqueness whenever a path exists, but says nothing by itself about existence between different components. Assuming a unique path while trying to prove that a connected graph is acyclic is circular.
The one-vertex graph satisfies both conditions and has no edges; it is the base case of the edge-count proof. For forests, the same reasoning applies separately to each connected component, including isolated vertices.