Tree (graph theory)

A tree is a nonempty connected graph containing no graph cycle. Think of seven locations joined so that everyone can reach everyone else, but no connection supplies an alternative route. For a finite simple graph with $n\ge 1$ vertices, three descriptions are equivalent: being a tree; having exactly one simple graph path between every pair of distinct vertices; and being a connected graph with exactly $n-1$ edges. Here a simple graph path repeats no vertex. Connectedness in the last description is essential. ^[ref]

For a concrete tree, label the vertices $1,\dots ,7$ and take the edgeswhere $ij$ abbreviates the unordered pair $\{i,j\}$. There are seven vertices and six edges. The unique graph path from $4$ to $7$ is $4,2,1,3,6,7$, using five edges. The degree sequence in label order is $(2,3,2,1,1,2,1)$: its sum is $12=2\cdot 6$, as the degree-sum formula predicts. Each of $4,5,7$ is a leaf of a graph, having vertex degree one.

Deleting edge $13$ leaves precisely two connected components of a graph, on $\{1,2,4,5\}$ and $\{3,6,7\}$. Every edge of a tree is a bridge in a graph. Instead add edge $57$ to the original tree: it closes the unique existing graph path $5,2,1,3,6,7$ into exactly one graph cycle. Thus a tree provides economical connections with no redundancy: a single failed link separates locations. Every finite tree with at least two vertices has at least two instances of a leaf of a graph; the endpoints of a longest graph path supply them. ^[ref]

The number $n-1$ alone proves nothing about connectedness: a cycle graph on $1,\dots ,6$ together with an isolated vertex $7$ has seven vertices and six edges, yet is disconnected. Briefly, two different simple graph paths between the same vertices would contain a graph cycle. Repeatedly removing a leaf of a graph and its incident edge proves the tree count $n-1$ by mathematical induction, starting with one vertex and no edges.