Is the empty graph a tree?

Question

This is a boring, technical question that I stumbled upon while making a contribution to Sage. I would still like to hear a constructive answer so hopefully the question does not get closed.

The question is the following.

How many spanning trees does the empty graph $E$ have?

According to Sage it has 1, while Mathematica claims $\tau(E) = 0.$ Now the only subgraph of $E$ is $E$ hence this question can be rephrased as

Is $E$ a tree?

One characterization says that a tree is a connected graph with $n$ vertices and $n-1$ edges and would imply that $E$ is not a tree. However if we define a tree as a connected acyclic graph then $E$ is clearly a tree.

It appears that as far as Kirchhoff is concerned any value would do since $$\rm{adj}(\mathcal{L}(E)) = \mathcal{L}(E) = k\mathcal{L}(E)$$ for any $k.$

Hence what I am wondering is

Are there any wider reasons in defining $E$ to (not) be a tree?

Answer 1

In a paper "Is the null-graph a pointless concept?" Harary and Read examine reasons for assigning certain properties to the empty graph. They observe that from the enumeration perspective it appears to be convenient to consider the empty graph as a forest, but not a tree.

Answer 2

The whole discussion seems to devolve on whether the empty graph (or empty space) should be considered "connected". Angelo and I are of the school that it should not, but this should be explained since some of the traditional definitions of "connected" apparently allow the empty space to be connected.

A general abstract context is as follows. Let $C$ be a category with finite coproducts with the property that for any two objects $a$, $b$ (whose coproduct is denoted $a+b$), the canonical functor

$$C/a \times C/b \to C/(a+b): (x \to a, y \to b) \mapsto (x + y \to a + b)$$

is an equivalence. Such a category is said to be extensive. The category of topological spaces is extensive, the category of graphs is extensive, any topos is extensive, and there are many, many other examples.

Now, say an object $a$ in an extensive category is connected if the functor

$$\hom(a, -): C \to Set$$

preserves binary coproducts (whence it can be shown to preserve finite coproducts). This is a fundamental definition; see the nLab for an extended discussion. Under this definition, the empty space (the empty graph, etc.), i.e., the initial object, is not connected.

An equivalent definition is to say $c$ is connected if, whenever $c \cong a + b$, exactly one of $a, b$ is inhabited. If one insists that the empty space should be connected, then change the word "exactly" to "at most", and instead of saying the canonical map $\hom(c, x) + \hom(c, y) \to \hom(c, x + y)$ is an isomorphism, say it is merely surjective. However, most results come out more cleanly by working with the definition above, which disqualifies the empty set.

Compare the notion of prime ideal: working in the lattice of ideals of a p.i.d. $R$ where $\leq$ is given by reverse inclusion, the coproduct or join of ideals $a, b$ is $ab$, the initial ideal is $R$, and we say an ideal $p$ is prime if $p \neq R$ and $p \leq ab$ implies $p \leq a$ or $p \leq b$. The condition $p \neq R$ is considered fundamental to the definition of prime. Without it, we no longer have e.g. unique decomposition of integers into prime factors (compare the fact that every graph is uniquely a coproduct of connected graphs under our definition, but this is not so if the empty graph is considered to be connected). See also the numerous examples in the nLab discussion "too simple to be simple"; for example, $1$ is too simple to be a prime, and the zero module is considered too simple to be a simple module.

Every acyclic graph (a forest) is uniquely a coproduct of acyclic connected graphs (i.e., trees) under our definition of connectedness. This includes the empty forest. So a forest can be empty, but a tree cannot.

Answer 3

I don't consider the empty graph to be a tree, or a connected graph, because I prefer the following definition of connectedness: A graph $G$ is connected if, whenever it is the disjoint union of a family of graphs, then one of the graphs in that family is $G$ itself. The empty set does not satisfy this, because it is the disjoint union of the empty family.

A category-theoretic version would define connectedness to mean that, whenever $G$ is expressed as a coproduct, one of the coproduct injections must be an isomorphism. That's less elegant than the "Hom preserves coproducts" definition in Todd Trimble's answer, but I think it's closer to common, non-category-theoretic intuition.

The same style of definition deals (in my opinion correctly) with the question whether 1 is prime. Define a positive integer $p$ to be prime iff, whenever it is expressed as a product, one of the factors is $p$ itself. This definition makes 1 not prime, because it is the product of the empty family.

Answer 4

Something is connected if the number of its connected components is equal to one.

That being said, in one of my papers, I have sometimes felt the need to say that an object $X$ was either connected or empty. The language I eventually decided to use was: $$ \text{``Let $X$ be a connected possibly empty ...''} $$

Answer 5

In Bourbaki's terminology, the empty graph is a tree - cf. LIE.IV.Annex.3.

Answer 6

I checked Reinhard Diestel's textbook on Graph Theory. p.2

A graph of order 0 or 1 is called trivial. Sometimes, e.g. to start an induction, trivial graphs can be useful; at other times they form silly counterexamples and become a nuisance. To avoid cluttering the text with non-triviality conditions, we shall mostly treat the trivial graphs, and particularly the empty graph, with generous disregard.

Only nonempty graphs are defined to be connected. (p.9)

Answer 7

The empty structure is ''disconnected'' and the definition of a tree is ''connected acyclic graph''.

For example to get from the generating series $G(t)$ of a connected species to the generating series of the set of its structures $F(t) $ the formula is $F(t) = \exp(G(t)) = 1 + ... $. This $1$ at degree zero is the empty structure.

Answer 8

The correct formulation of Kirchoff's Theorem is the following result, which does not require any connectedness assumption on the graph $G$, and does not lead to false expectations when the graph is empty.

Let $\Delta\colon L^2(G)\to L^2(G)$ be the Laplacian on a finite graph $G$. Then $\ker(\Delta)$ is the space of locally constant functions on $G$; its dimension is the number of connected components of $G$. Let $L^2_0(G)$ be the orthogonal of $\ker(\Delta)$, a subspace stable under $\Delta$. Then $\det(\Delta|L^2_0(G))$ is the number of maximal forests in $G$.

Answer 9

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.

Answer 10

Some comments above discuss the question from the point of view of homology. I'd like to expand on these.

You might consider a tree to be an abstract simplicial complex of dimension at most 1 that has trivial reduced homology. Note that we probably want to include the simplicial complex with vertex as its facet as a tree (so "dimension at most 1" is preferable to "dimension exactly 1"). And I regard reduced simplicial homology as the homology theory where we treat the empty set as a face.

So from this point of view, it depends which empty graph you are considering. In $\Delta = \{ \emptyset \}$, the chain complex is nontrivial in the -1 degree, yielding nontrivial $\tilde{H}_{-1}$. In $\Gamma = \emptyset$, the chain complex and homology are both everywhere 0. Accordingly, if we are to follow this, then it makes sense to consider that $\Gamma$ is a tree, but $\Delta$ is not.

A reference that takes this point of view is Ehrenborg and Hetyei's paper The topology of the independence complex, which considers $\Delta$ as a $(-1)$-dimensional sphere and $\Gamma$ as a $(-1)$-dimensional simplex.