Is the empty graph a tree? - MathOverflow

Is the empty graph a tree?

2013-02-01T19:33:47Z

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 by Sergey Norin for Is the empty graph a tree?

2013-02-01T20:15:37Z

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 by Aaron Meyerowitz for Is the empty graph a tree?

2013-02-01T20:26:51Z

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

for all $u \in S$ the set $\{x \mid x \preceq u\}$ is totally ordered by $\prec$
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 by Samuel Vidal for Is the empty graph a tree?

2013-02-01T21:07:45Z

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 by Fred Rohrer for Is the empty graph a tree?

2013-02-01T21:30:54Z

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

Answer by Todd Trimble for Is the empty graph a tree?

2013-02-02T08:46:15Z

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 by Andreas Blass for Is the empty graph a tree?

2013-02-02T14:32:16Z

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 by André Henriques for Is the empty graph a tree?

2013-02-04T23:26:00Z

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

Answer by ACL for Is the empty graph a tree?

2013-02-05T08:05:44Z

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 by Günter Rote for Is the empty graph a tree?

2013-02-07T14:22:29Z

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)