Trees and Networks - Key Properties

Trees possess unique structural properties that distinguish them from general graphs and enable efficient algorithms. Understanding these characterizations provides powerful tools for proving properties and designing algorithms.

DefinitionEquivalent Characterizations of Trees

For a graph $G$ with $n$ vertices, the following are equivalent:

$G$ is a tree (connected and acyclic)
$G$ is connected and has $n-1$ edges
$G$ is acyclic and has $n-1$ edges
$G$ is connected and removing any edge disconnects it
$G$ is acyclic and adding any edge creates exactly one cycle
There is exactly one path between any two vertices

Proof sketch: We prove $(1) \Rightarrow (2) \Rightarrow (3) \Rightarrow (1)$ .

$(1) \Rightarrow (2)$ : Induction on $n$ . Base: $n=1$ has 0 edges. Inductive step: Remove a leaf (exists since acyclic and connected), apply induction to smaller tree.

$(2) \Rightarrow (3)$ : If $G$ had a cycle, removing one edge would keep it connected, contradicting minimality of edge count for connectivity.

$(3) \Rightarrow (1)$ : $G$ is acyclic. If disconnected with $k \geq 2$ components, each component is acyclic with $n_i$ vertices and $n_i - 1$ edges. Total edges: $\sum(n_i - 1) = n - k \leq n - 2$ , contradiction.

DefinitionCenter of a Tree

The center of a tree is the set of vertices minimizing the maximum distance to other vertices (eccentricity). Every tree has either one center vertex (forming a central tree) or two adjacent center vertices (forming a bicentral tree).

The center can be found by repeatedly removing leaves until one or two vertices remain.

DefinitionTree Traversals

Depth-First Search (DFS): Explore as deeply as possible before backtracking. Orders:

Preorder: Process root, then left subtree, then right subtree
Inorder: Process left subtree, then root, then right subtree
Postorder: Process left subtree, then right subtree, then root

Breadth-First Search (BFS): Process vertices level by level from the root.

DFS and BFS both run in $O(n)$ time on trees with $n$ vertices.

ExampleBinary Tree Properties

A full binary tree has every vertex with 0 or 2 children. A complete binary tree has all levels filled except possibly the last, which is filled left-to-right.

For a binary tree with $n$ vertices, $i$ internal vertices, and $\ell$ leaves:

$n = i + \ell$
In a full binary tree: $\ell = i + 1$ (one more leaf than internal vertex)
Maximum height: $n-1$ (degenerate to path)
Minimum height: $\lfloor \log_2 n \rfloor$ (complete tree)

DefinitionCatalan Number Connection

The number of full binary trees with $n$ internal vertices equals the Catalan number $C_n = \frac{1}{n+1}\binom{2n}{n}$ .

These also count:

Ways to parenthesize $n+1$ factors
Binary trees with $n+1$ leaves
Dyck paths of length $2n$

Remark

Tree decompositions extend tree properties to general graphs. Treewidth measures how "tree-like" a graph is: graphs with small treewidth admit efficient dynamic programming algorithms. Many NP-hard problems become tractable on graphs of bounded treewidth, including vertex cover, independent set, and graph coloring. This connection between tree structure and computational complexity is fundamental in parameterized complexity theory and has applications in database query optimization and computational biology.

These properties make trees one of the most well-understood and algorithmically tractable graph classes.