Trees and spanning-tree structure

A tree is a finite, nonempty, connected simple undirected graph with no cycle. Between every pair of vertices there is at least one simple path by connectedness. There cannot be two different simple paths with the same endpoints: follow them to their first divergence and subsequent reunion to obtain a cycle. Conversely, if every pair has exactly one simple path, the graph is connected and cannot contain a cycle, since two portions of that cycle would give competing paths.

Every tree with at least two vertices has a leaf, meaning a degree-one vertex. Choose a longest simple path. An endpoint cannot have an extra neighbor outside the path, which would extend it, or an extra neighbor farther along the path, which would create a cycle. Both endpoints are therefore leaves. Finiteness matters to the longest-path argument; an infinite doubly infinite chain has no leaves. The one-vertex tree is also a special case: its sole vertex has degree zero.

Remove a leaf and its incident edge from a tree with at least two vertices. The remaining graph stays connected because a simple path between remaining vertices never needs the leaf, and deleting edges cannot create cycles. Induction from the one-vertex tree therefore gives one fewer edge than vertices. A forest is a graph with no cycles, so applying the formula to each of its components gives the more general edge count in the equation below.

The count becomes a characterization when combined with another property. A connected graph with $n-1$ edges is a tree: repeatedly delete cycle edges while maintaining connectedness, producing a spanning tree with $n-1$ edges, so there were no surplus edges to delete. Edge count alone is insufficient. A triangle together with an isolated vertex has four vertices and three edges but is disconnected and contains a cycle. Always track which extra hypothesis converts a numerical identity into a structural certificate.

Every finite connected graph contains a spanning tree, a subgraph that retains all vertices and is a tree. One construction repeatedly removes an edge on a cycle; the remaining part of that cycle still connects its endpoints, so connectivity survives. Another keeps only predecessor edges from a search. These arguments establish existence without assigning edge weights. A minimum spanning tree requires an additional optimization question about total weight and should not be confused with an arbitrary search tree.

Adding a new edge between two vertices of a tree closes exactly one cycle: the new edge plus the unique old path between its endpoints. Removing any edge of that cycle returns a spanning tree. By contrast, deleting any original tree edge separates the vertices into two components, since an alternate connection would have formed a cycle. This exchange picture is the basis of many efficient algorithms and also explains the resilience tradeoff: extra edges buy alternate routes, while a bare tree makes every edge a bridge.