Trees

How to contact me.

Definitions

A graph is acyclic if it has no cycles. An acyclic graph is also called a forest. A tree is a connected, acyclic graph. Thus every connected component of a forest is a tree. A spanning tree of a graph G is a subgraph T of G which is a tree and which satisfies |V(T)|=V|(G)|.

Easy Theorems

If T is a tree, then |V(T)|=E|(T)|+1. Any tree with at least two vertices must have a vertex of degree one. Alternately, one could define a tree as a connected graph T satifying |V(T)|=E|(T)|+1 or as an acyclic graph T satifying |V(T)|=E|(T)|+1. Every connected graph must have a spanning tree.

The number of spanning trees of a connected graph can be deduced from the Tutte polynomial or computed efficiently using the Matrix Tree Theorem.

Last modified January 18, 1996, by S.C. Locke.