Return to Answer

I think it just depends on how you want to use it. I will claim that sometimes the empty graph is best considered a tree and even a rooted tree but other times, neither. Even the one vertex tree is a little odd, it is the only tree with a degree zero vertex.

The Catalan numbers count many kinds of trees. In an Ordered Binary Tree each node may have up to two children left and/or right. If we let $C_n$ be the number of such with $n$ nodes then could exclude the empty tree and say

• $C_1=1$

• $C_{n+1}=C_n+C_n+\sum_i=1^{n-1}C_iC_{n-i}$

The first two terms for the case of only one child. But it is nicer to think of the left and right children as being themselves binary trees, both present, but perhaps one or both the empty tree.

• $C_0=1$

• $C_{n+1}=\sum_0^nC_iC_{n-i}$.

I think that the second approach is nicer. Particularly for the analogous situation with trinary trees.

A Full Ordered Binary Tree is as above except that a node may have either $0$ or $2$ children (thought of as nodes). There is a natural bijection between OBTs (including the empty tree) having $n$ nodes and FOBTs (not including the empty tree) having $n+1$ leaf nodes. In one direction assign each leaf node two children and in the other remove all the leaf nodes.

So here we interpret $C_n$ as the number of FOBTs with $n+1$ leaf nodes and do not bother to consider the empty tree as a FOBT.

Given a non-associative product, an expression $x_1\cdot x_2 \cdot x_k$ needs parentheses to be evaluated. We can use a FOBT with $k-1$ non-leaf nodes corresponding to the multiplications and $k$ leaves corresponding to the variables. Then $C_0$ counts the one vertex tree from the "product" $x_1.$ Now there seems no reason to count the empty tree. Of course we do like the empty product, but that is not especially relevant.

If we want to have a definition of rooted tree which does not specifically mention "the root" then we can say that a rooted tree is precisely a finite partial order $(S,\prec)$ such that

1. for all $u \in S$ the set $\{x \mid x \preceq u\}$ is totally ordered by $\prec$
2. for all $u,v \in S$ there is a common lower bound.

If we can get away with that, then the empty order is an order.

I think it just depends on how you want to use it. I will claim that sometimes the empty graph is best considered a tree and even a rooted tree but other times, neither. Even the one vertex tree is a little odd, it is the only tree with a degree zero vertex.

The Catalan numbers count many kinds of trees. In an Ordered Binary Tree each node may have up to two children left and/or right. If we let $C_n$ be the number of such with $n$ nodes then could exclude the empty tree and say

• $C_1=1$

• $C_{n+1}=C_n+C_n+\sum_{i=1}^{n-1}C_iC_{n-i}$

The first two terms for the case of only one child. But it is nicer to think of the left and right children as being themselves binary trees, both present, but perhaps one or both the empty tree.

• $C_0=1$

• $C_{n+1}=\sum_0^nC_iC_{n-i}$.

I think that the second approach is nicer. Particularly for the analogous situation with trinary trees.

A Full Ordered Binary Tree is as above except that a node may have either $0$ or $2$ children (thought of as nodes). There is a natural bijection between OBTs (including the empty tree) having $n$ nodes and FOBTs (not including the empty tree) having $n+1$ leaf nodes. In one direction assign each leaf node two children and in the other remove all the leaf nodes.

So here we interpret $C_n$ as the number of FOBTs with $n+1$ leaf nodes and do not bother to consider the empty tree as a FOBT.

Given a non-associative product, an expression $x_1\cdot x_2 \cdot x_k$ needs parentheses to be evaluated. We can use a FOBT with $k-1$ non-leaf nodes corresponding to the multiplications and $k$ leaves corresponding to the variables. Then $C_0$ counts the one vertex tree from the "product" $x_1.$ Now there seems no reason to count the empty tree. Of course we do like the empty product, but that is not especially relevant.

If we want to have a definition of rooted tree which does not specifically mention "the root" then we can say that a rooted tree is precisely a finite partial order $(S,\prec)$ such that

1. for all $u \in S$ the set $\{x \mid x \preceq u\}$ is totally ordered by $\prec$
2. for all $u,v \in S$ there is a common lower bound.

If we can get away with that, then the empty order is an order.

I don't see a whole bunch of use for it. However if the empty graph is a connected graph and every connected graph has a spanning tree then...

It all depends what you want to do with it. I thought of generating functions. The first article in a Google search says "It will turn out to work better if we ... do not count the empty tree as a rooted tree." So that indicates that "who knows, it could have been better the other way but it isn't." It also seems to say "it is a tree but not a rooted one." Then again, the author does not need to take a position since rooted trees are what is needed.

Would it be so perverse to say that a rooted tree is precisely a finite partial order $(S,\prec)$ such that

If we can get away with that then the empty order is an order...

For the purposes of this question let me stipulate a structure called an Rooted Oriented Trinary Tree (a ROTT.) This is simply a rooted tree such that each node may have a left, and/or middle, and/or right child. So, it might have only a middle and a right child.

It might be convenient to inductively define

1. The empty graph is a ROTT
2. any ordered tripple $[T_{\ell},T_m,T_r]$ of ROTTs is a ROTT
3. That is all ROTTs

Sure you could avoid it, but in that case It will turn out to work better if we "count the empty tree as a rooted tree."

I can't remember the venerable book I first learned the theory of convex sets from, but I recall that the introduction said something like "to save ink we will not mention the word "nonempty" in the statement of theorems." The point being that we want the intersection of convex sets to be convex and there is an operation which sends $A,B$ to the convex hull of their union and the empty set is the identity for this operation. But we ignore it when it suits us.

I think it just depends on how you want to use it. I will claim that sometimes the empty graph is best considered a tree and even a rooted tree but other times, neither. Even the one vertex tree is a little odd, it is the only tree with a degree zero vertex.

The Catalan numbers count many kinds of trees. In an Ordered Binary Tree each node may have up to two children left and/or right. If we let $C_n$ be the number of such with $n$ nodes then could exclude the empty tree and say

• $C_1=1$

• $C_{n+1}=C_n+C_n+\sum_i=1^{n-1}C_iC_{n-i}$

The first two terms for the case of only one child. But it is nicer to think of the left and right children as being themselves binary trees, both present, but perhaps one or both the empty tree.

• $C_0=1$

• $C_{n+1}=\sum_0^nC_iC_{n-i}$.

I think that the second approach is nicer. Particularly for the analogous situation with trinary trees.

A Full Ordered Binary Tree is as above except that a node may have either $0$ or $2$ children (thought of as nodes). There is a natural bijection between OBTs (including the empty tree) having $n$ nodes and FOBTs (not including the empty tree) having $n+1$ leaf nodes. In one direction assign each leaf node two children and in the other remove all the leaf nodes.

So here we interpret $C_n$ as the number of FOBTs with $n+1$ leaf nodes and do not bother to consider the empty tree as a FOBT.

Given a non-associative product, an expression $x_1\cdot x_2 \cdot x_k$ needs parentheses to be evaluated. We can use a FOBT with $k-1$ non-leaf nodes corresponding to the multiplications and $k$ leaves corresponding to the variables. Then $C_0$ counts the one vertex tree from the "product" $x_1.$ Now there seems no reason to count the empty tree. Of course we do like the empty product, but that is not especially relevant.

If we want to have a definition of rooted tree which does not specifically mention "the root" then we can say that a rooted tree is precisely a finite partial order $(S,\prec)$ such that

If we can get away with that, then the empty order is an order.

I don't see a whole bunch of use for it. However if the empty graph is a connected graph and every connected graph has a spanning tree then...

It all depends what you want to do with it. I thought of generating functions. The first article in a Google search says "It will turn out to work better if we ... do not count the empty tree as a rooted tree." So that indicates that "who knows, it could have been better the other way but it isn't." It also seems to say "it is a tree but not a rooted one." Then again, the author does not need to take a position since rooted trees are what is needed.

I guess one can always say "non-empty" trees if needed.

I don't see a whole bunch of use for it. However if the empty graph is a connected graph and every connected graph has a spanning tree then...

It all depends what you want to do with it. I thought of generating functions. The first article in a Google search says "It will turn out to work better if we ... do not count the empty tree as a rooted tree." So that indicates that "who knows, it could have been better the other way but it isn't." It also seems to say "it is a tree but not a rooted one." Then again, the author does not need to take a position since rooted trees are what is needed.

Would it be so perverse to say that a rooted tree is precisely a finite partial order $(S,\prec)$ such that

1. for all $u \in S$ the set $\{x \mid x \preceq u\}$ is totally ordered by $\prec$
2. for all $u,v \in S$ there is a common lower bound.

If we can get away with that then the empty order is an order...

For the purposes of this question let me stipulate a structure called an Rooted Oriented Trinary Tree (a ROTT.) This is simply a rooted tree such that each node may have a left, and/or middle, and/or right child. So, it might have only a middle and a right child.

It might be convenient to inductively define

1. The empty graph is a ROTT
2. any ordered tripple $[T_{\ell},T_m,T_r]$ of ROTTs is a ROTT
3. That is all ROTTs

Sure you could avoid it, but in that case It will turn out to work better if we "count the empty tree as a rooted tree."

I can't remember the venerable book I first learned the theory of convex sets from, but I recall that the introduction said something like "to save ink we will not mention the word "nonempty" in the statement of theorems." The point being that we want the intersection of convex sets to be convex and there is an operation which sends $A,B$ to the convex hull of their union and the empty set is the identity for this operation. But we ignore it when it suits us.