Trees

• A forest is an acyclic graph.

• A tree is a connected, acyclic graph

• (Wilson 9.1) Let be a graph with vertices. The following are equivalent.

1. is a tree
2. contains no cycles and has edges
3. is connected and has edges
4. is connected and each edge is a bridge
5. Any two vertices of are connected by exactly one path
6. contains no cycles but the addition of any new edge creates exactly one cycle.

• A leaf is a vertex in a forest with degree .

• A tree is rooted if one vertex has been designated the root.

• Let be the spanning tree of a connected graph. The cotree is defined as the subgraph obtained by

  That is the graph whose edges are not in the spanning tree.

• For directed graphs, we define an arborescence or out-branching as a directed acyclic graph such that a vertex is denoted as the root, and there is a directed path from to for any other vertex . We say that it is a -arborescence.

  Similarly, an anti-arborescence or in-branching is one where there exists a directed path from to .

Theorems §

• (Wilson 9.2) If is a forest with vertices and components, then has edges
• (Wilson 9.2x) Any tree on vertices has at least two leaves.
• (Wilson 9.3b) Each cycle of has an edge in common with the cotree of .
• (Wilson 9.3b) Each cycle of has an edge in common with .
• (Wilson e9.3.1) Every tree is bipartite
• (Wilson e9.9) A tree has either one center or two adjacent centers ¹

• (Wilson 33.7) A graph splits into forests if and only if for all subgraphs ,

  Where is the number of edges of .

Topics §

• Spanning Trees and Forests
• Labelled Trees

Links §

• Wilson

• Graph Connectivity - more on connectivity.

• Trails, Walks, Paths and Cycles - more on cycles.

Footnotes §

1. This is based on deleting vertices starting from the leaf nodes. ↩