Contents

Idea

A tree is a connected graph without cycles. Some notions of tree (such as planar tree) consider extra structure or properties as well, but the baseline notion is tree as acyclic connected graph.

Trees are fundamental combinatorial objects which appear in a wide variety of guises. Some are given below.

Definitions

As graphs

Recall that an undirected graph $G$ consists of a set $V$ of vertices and a set $E$ of unordered pairs of vertices. A path in $G$ is a finite sequence of vertices $x_0,\dots ,x_n$ such that each pair $x_i{x}_{i+1}$ belongs to $E$. If $x_n=x_0$, then the path is called a cycle. A graph is connected if it is nonempty and if for every distinct pair of vertices $x,y$, there is a path for which $x_0=x$ and $x_n=y$. A graph is acyclic if it has no cycles; an acyclic graph is also called a forest. A tree is a connected forest.

Each forest is a disjoint sum (a coproduct in the category of graphs) of trees. Removal of a vertex of a tree (and any edges incident to it) results in a forest.

Not all authors include nonemptiness as part of the notion of connectedness. See connected space for commentary on this. Forests on the other hand may be empty.

As spaces

A tree is a 1-dimensional CW-complex which is contractible, i.e., homotopy equivalent to a point.

In this language, a graph is simply a 1-dimensional CW-complex; more precisely, we mean a CW-presentation and not merely a space that can be so presented. A forest is then a 1-dimensional CW-complex with vanishing first homology group with integral coefficients, and a tree is a connected forest.

For finite graphs $G$ as CW-complexes, one has the useful Euler formula:

where $c_i$ is the number of $i$-cells and $h_i$ is the rank of the homology group $H_i(G;\mathbb{Z})$. This gives a useful criterion for a graph to be a tree: that it be connected ($h_0=1$) and that the number of vertices $c_0$ be 1 greater than the number of edges $c_1$.

As digraphs

A rooted tree is a directed graph $G$ such that the free category generated by $G$ has a terminal object, called the root of $G$. (Thus for every vertex $x$ in $G$ there is exactly one directed path from $x$ to the root. It follows easily that the free category is a poset. There is no significant change in content if “terminal” here is replaced by “initial”; we can distinguish the conventions by a tree directed towards the root rather than away from the root.)

A rooted forest is a coproduct of rooted trees, and again we have the fundamental fact that there is a natural equivalence of categories

which in one direction is the functor which sends a tree to the forest which results by excising the root and all edges incident to it, and in the other sends a forest to the tree gotten by adjoining a new root and joining the roots of the forest to that new root by new edges.

A tree in the form of an undirected graph together with a chosen vertex can be regarded as a rooted tree in digraph form (with root the chosen vertex), by orienting all edges in the direction of paths going to the root. The category of rooted trees has very nice categorical properties not shared by the category of unrooted trees; see the following section.

As functors

Let $\mathbb{N}$ be the totally ordered set of natural numbers $0\le 1\le 2\le \dots$, viewed as a category. A rooted forest is a presheaf on $\mathbb{N}$, i.e., a functor

to “the” category of sets. A rooted tree is a forest for which $F(0)$ is terminal (a point).

In this case, we get from a tree as functor $F$ to a tree as digraph by passing to the category of elements $\mathrm{El}(F)$. The vertices of the digraph are the elements, and the edges are those morphisms of $\mathrm{El}(F)$ which map to morphisms $i+1\to i$ in ${\mathbb{N}}^{\mathrm{op}}$. Notice that ${\mathbb{N}}^{\mathrm{op}}$ is itself (the free category on) a tree as digraph, one that is terminal in the category of forests.

This description makes it clear that the category of forests is a (presheaf) topos, indeed a Grothendieck topos; therefore the category of trees, which is equivalent, is also a topos.

If we replace $\mathrm{Set}$ here by the category of totally ordered sets $\mathrm{Tos}$, then we may define a planar forest as a functor

As operations

Let $F$ denote the Lawvere theory freely generated by $n$-ary operations ${\theta }_n:x^n\to x$, one for each arity $n\ge 1$. A (finite) planar forest is a morphism $\varphi :x^n\to x^m$ in $F$; a (finite) planar tree is a morphism $\varphi :x^n\to x$.

The previous description is more a theorem than definition, and points up a typical way in which rooted trees are used in general recursive constructions, largely on the basis of the fundamental equivalence between forests and trees. In the case of trees as operations, the basic recursive construction is this: given a planar forest $F:x^n\to x^m$, one may form a planar tree by composing with the $m$-ary generator $\theta :x^m\to x$, and all planar trees arise in just this way. This mirrors the way in which the trees of a forest can be joined into a larger tree by joining them to a new root.

Fancier versions of this basic recursive construction may involve “colored trees”, “cherry trees”, and so on, and figure prominently in the theory of operads, especially in the construction of free operads.

In fact, this type of recursivity is at the root (pun perhaps intended) of the cumulative hierarchy? conception of sets in a material set theory like ZFC set theory: all sets are collections of sets $\{x_1,\dots ,x_n\}$, and all sets are formed in this way. In order to found this conception on trees in a way that accepts the axiom of foundation, one must restrict to well-founded trees. A tree (pictured as a free category on a digraph, i.e., as a certain poset $P$) is well-founded if every object of $P^{\mathrm{op}}$ is bounded above by a maximal element, or equivalently if there are no infinite chains $x_0<x_1<\dots$ in $P^{\mathrm{op}}$ starting from the root $x_0$. (Chains starting from the root are also called branches.) See well-founded relation for other formulations of this definition (including those suitable for constructive mathematics; see pure set for details on this construction of the cumulative hierarchy, including using arbitrary trees for ill-founded sets.

To be continued…