Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

share|improve this question
34  
A connected space should always be assumed to be non-empty, for the same reason that 1 is not considered to be a prime. –  Angelo Feb 1 '13 at 19:52
5  
I agree with Angelo: a "connected acyclic graph" must have the homology of a point (this is what acyclic means topologically) so even this definition does not lead to the conclusion that one should call the empty graph a tree. –  Vidit Nanda Feb 1 '13 at 20:02
5  
In topology, a useful convention is to say that a space $X$ is $k$-connected if every map of an $\ell$-sphere into $X$ with $\ell \leq k$ can be extended to a map of an $(\ell+1)$-ball. With this convention, all spaces are $(-2)$-connected, and all nonempty spaces are $(-1)$-connected. So to a topologist, the empty graph is not $1$-connected, so it is not a tree. –  Andy Putman Feb 1 '13 at 20:41
38  
Is the empty graph a tree? No, but it's a forest. –  Gerald Edgar Feb 1 '13 at 20:55
13  
To expand upon Angelo's analogy: one needs to exclude 1 from the set of primes if one wants to decompose every natural number uniquely (up to permutation) as the product of primes (i.e. the fundamental theorem of arithmetic). Similarly, one needs to exclude the empty set from the set of trees if one wants to decompose every forest uniquely (up to permutation) as the disjoint union of trees. –  Terry Tao Feb 2 '13 at 6:08

9 Answers 9

up vote 39 down vote accepted

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.

share|improve this answer
10  
Yes, it's the union of zero trees. –  David Roberts Feb 4 '13 at 4:03
23  
... proving that it is possible to see the forest for the trees. –  Terry Tao Feb 4 '13 at 18:56

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.

share|improve this answer
7  
Well of course a rooted tree can't be empty, because it has a root. –  Todd Trimble Feb 2 '13 at 13:57
    
Todd, that only holds if it has vertices! –  Aaron Meyerowitz Feb 3 '13 at 3:43
1  
All the definitions of rooted tree I've seen (except in your answer) stipulate a distinguished node called the root. –  Todd Trimble Feb 3 '13 at 5:17
    
Of course. I'm just saying that one could decide to do so. As I said, it does seem a stretch and not of much obvious use. –  Aaron Meyerowitz Feb 3 '13 at 5:52
    
May be a way to clarify the question is to consider not the graph in itself but within its family. Consider The family (species) of connected graphs $G^c$ and the family of not necessarily connected graphs $G$. The relation between them is: $$G\simeq E(G^c)$$ where E stands for the species of sets. This natural isomorphism comes from existence and unicity of a decomposition of a graph (in $G$) in its connected components (in $G^c$). If you work out the details, $G^c$ can't have any graph of size zero. This is why you better not see the empty graph as connected. –  Samuel Vidal Feb 3 '13 at 16:23

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.

share|improve this answer
5  
I like to say that a space is disconnected if it may be partitioned into two (nonempty) closed sets, and that a space is connected if it is not disconnected and not empty, either. In other words, I call the empty space neither connected nor disconnected. But that's just me. –  Tom Goodwillie Feb 1 '13 at 23:51
1  
I sometimes like to call the empty space the (unique) example of an unconnected space (neither connected (i.e. one connected component) nor disconnected (i.e. two or more connected components)). –  Terry Tao Feb 4 '13 at 18:41
    
I agree, and would point out, in case anyone is uncomfortable with "disconnected" and "connected" not forming a dichotomy, that neither do "closed" and "open". –  Andrew D. King Feb 5 '13 at 19:10
    
"disconnected" and "connected" not forming a dichotomy : brilliant, that's the point ! –  Samuel Vidal Feb 9 '13 at 18:08

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

share|improve this answer
7  
and (consistently) in Bourbaki, the empty space is connected. –  YCor Feb 1 '13 at 23:16
6  
It'd be nice to know what individual to blame for this (according to the impressive consensus here) error. –  Allen Knutson Feb 4 '13 at 3:40
1  
I would say, that the one to blame are the same who say nonpositive for negative, and so on. –  ACL Feb 4 '13 at 22:34
    
@ACL: As far as I know, Bourbaki does not use "nonpositive". –  Fred Rohrer Feb 5 '13 at 6:11
    
@Fred: well observed :-) –  ACL Feb 7 '13 at 22:22

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.

share|improve this answer

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.

share|improve this answer
1  
Then $2$, being equal to $(-1)\times (-2)$, is not prime? –  ACL Feb 5 '13 at 0:57
    
I was hoping that it was clear that the definition was for positive integers, even though I admittedly said "positive integer" only once, modifying $p$. Indeed, if you allow factors to be things other than positive integers, then you have not only the problem you exhibited but also $2=(1+i)(1-i)=(4\pi)(\pi/2)$, etc. So please understand "expressed as a product" to mean "expressed as a product of positive integers. –  Andreas Blass Feb 5 '13 at 14:03
    
Understood. It was kind of a joke! I'm sorry. –  ACL Feb 5 '13 at 21:28
    
Isn't the empty graph the disjoint union of any family (of any cardinality) of empty graphs? –  Greg Martin Feb 26 '13 at 23:09
1  
@Greg: Yes, but that decomposition doesn't serve as a counterexample to the assertion that the empty graph is connected. That decomposition contains isomorphs of the empty graph itself, as the definition of "connected" would require. What does serve as a counterexample is the decomposition as the disjoint union of the empty family of graphs; that family contains no isomorph of the empty graph (because it contains no graphs at all). –  Andreas Blass Feb 27 '13 at 2:31

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 ...''} $$

share|improve this answer
4  
Quite so. Moreover, a connected component is an equivalence class, and an equivalence class of an equivalence relation on a set is by definition nonempty. Therefore... –  Todd Trimble Feb 5 '13 at 0:07

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$.

share|improve this answer

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)

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.