Trees

Precise definition

A tree is a connected undirected graph with no cycles. For a finite simple graph with $n$ vertices, the following are equivalent: it is a tree; it is connected with $n-1$ edges; it is acyclic with $n-1$ edges; or every two vertices have exactly one simple path between them.

Notation and mathematical language

A leaf has degree 1 (except conventions for a one-vertex rooted tree). In a rooted tree, each non-root vertex has one parent; descendants, depth, and height depend on the chosen root. A spanning tree of a connected graph contains every vertex and a subset of edges forming a tree.

Conceptual picture

Trees have just enough edges for connectivity. Removing any edge disconnects a tree, while adding any new edge between existing vertices creates exactly one cycle. The unique-path property explains why hierarchical routes and recursive decompositions are unambiguous.

Conditions and key results

The $n-1$ edge characterization assumes a finite simple undirected graph and must be paired with connectivity or acyclicity; having $n-1$ edges alone is insufficient. Rooted terminology does not turn edges into directed edges unless direction is explicitly added.

A reliable strategy

1. Identify vertices and edges, then verify the graph type and number of components.
2. Test connectivity with a traversal and test acyclicity or use the $n-1$ theorem with its companion condition.
3. For rooted questions, mark the root before assigning parents, depths, and subtrees.
4. Check degree sum $2(n-1)$ and use the unique-path property to verify conclusions.

Fully worked example

Interpretation and application

Trees model file systems, organizational hierarchies, expression parsing, decision processes, and minimum-cost network backbones. A spanning tree preserves reachability but discards redundant routes, so it also removes fault tolerance present in cycles.

Common mistakes

Verification and reasonableness

• Confirm $|E|=|V|-1$ and independently verify connectivity or acyclicity.
• Check that every claimed pair has exactly one simple path.
• Use the handshaking lemma: a tree on $n$ vertices must have total degree $2n-2$.

Practice

1. How many edges does a tree with 20 vertices have?
2. What happens when one edge is removed from a tree?
3. Can a tree contain a cycle?

Further deduction

Every finite tree with at least two vertices has at least two leaves. Take a longest simple path. If an endpoint had another neighbour outside the path, the path could be extended; if it had another neighbour already on the path, a cycle would result. Thus each endpoint has degree one. The argument uses both finiteness, to ensure a longest path exists, and acyclicity, to rule out a return edge. This leaf fact supports induction on trees: remove a leaf and its incident edge, prove a property for the smaller tree, then attach the leaf again and show the property is preserved.

Related topics

• Graphs and Networks
• Algorithms
• Mathematical Induction