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?

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 01 '13 at 19:52
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 01 '13 at 20:02
Trees have roots and leaves, and when they are big enough they have branches as well. The one vertex graph is a not big tree, and the empty graph is not a tree, in my view. (The empty graph could be soil, or a dog, or a pink elephant, depending on the metaphor. Unless you need an additive identity though, the empty graph is not a tree.) Gerhard "It Is What You Need" Paseman, 2013.02.01 — Gerhard Paseman, Feb 01 '13 at 20:03
I wonder how sage does the calculation.
The complete graph on $k$ vertices is not $k$-connected. Here, the condition that a $k$-connected graph must have at least $k+1$ vertices is usually formulated explicitly. Setting $k=1$ it would mean that not even the graph with one vertex is 1-connected (=connected). So these analogies break down when it come to small values. — Günter Rote, Feb 01 '13 at 20:22
@Günter Rote Sage simply computes the subdivision of the Laplacian matrix and its determinant. — Jernej, Feb 01 '13 at 20:31
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 01 '13 at 20:41
@Angelo: I do not understand your argument. May I ask you to explain? — Fred Rohrer, Feb 01 '13 at 21:36
The number of trees of order $n$ is $n^{n-2}$ as everyone knows. So if the empty graph is a tree, which of the $0^{-2}$ possible trees is it? Which only goes to show that the question is not really meaningful except in the lexicographical sense. — Brendan McKay, Feb 02 '13 at 04:06
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 02 '13 at 06:08
Ah, I see. There seems to be some confusion between "connected spaces/graphs/things..." and "connected components of spaces/graphs/things...". If the empty thing is one of the former but none of the latter, then the problems about unique decompositions disappear. — Fred Rohrer, Feb 02 '13 at 08:17
If a tree falls in a forest and no one is around to notice, could it be empty? — Todd Trimble, Feb 02 '13 at 14:00
@Gerhard: Your comment works if a graph is a set of vertices and edges, but not if a graph is, say, an ordered pair consisting of a set of vertices and a set of edges. True, there is only one empty set, but "empty thing" need not mean "thing which is an empty set". If a topological space means an ordered pair $(X,T)$ where $X$ is a set and $T$ is a topology on $X$, then "empty space" means "space $(X,T)$ such that $X$ is empty". Tom "Talk to me about the empty set" Goodwillie — Tom Goodwillie, Feb 02 '13 at 14:20
@Andy Putnam: I am a big proponent of that definition of "$k$-connected", and in our world "1-connected" and "0-connected" are common synonyms for "path-connected" and "simply connected". But I gather that in graph theory "$k$-connected" has another unrelated meaning. — Tom Goodwillie, Feb 02 '13 at 14:41
I remember attending a MSRI conference in a previous millenium on universal algebra and category theory. I was wondering if a religious battle would break out over the notion of an empty algebra. Fortunately no blood was shed at that conference over the issue. This post reminds me of those years. Tom, I'm afraid I dealt more with nonempty algebras than potentially empty relational structures, so I am not entirely convinced by your comment. Not that you should worry. Gerhard "Pronounces Tom Devoid Of Blame" Paseman, 2013.02.02 — Gerhard Paseman, Feb 03 '13 at 05:09
@Angelo. In EGA, the empty scheme is connected, as witnessed by the statement of Zariski's connectedness theorem (III, 4.3.1), where Grothendieck and Dieudonné precise that the fibers are connected and non-empty. Of course it is not irreducible. — ACL, Feb 04 '13 at 22:42
Why would the empty graph have a spanning tree? Not every graph has a spanning tree! But every graph has a spanning forest. And the empty graph has exactly one. — ACL, Feb 04 '13 at 22:43
Just for fun, I browsed in the litterature to find what definition of connectedness was used. For Tom Dieck (Algebraic Topology), Munkres (Topology, A First Course), Ronnie Brown (Topology and groupoids), the empty set is connected. For Ethan Bloch, the empty space might be connected, but the first theorem he mentions is that the... non-empty connected sets of real numbers are the interval. :-) — ACL, Feb 05 '13 at 00:53
@Brendan McKay. Apparently, derivations of the $n^{n-2}$ formula all assume that $n\geq 1$. For example, in Kirchoff theorem, it is question of cofactor; and an empty matrix has no cofactor. In the Prüfer sequences story, you even need to assume that $n\geq 2$ since the Prüfer sequence has length $n-2$. — ACL, Feb 05 '13 at 01:04
By the way, Jernej, when making contributions to Sage, boring technical questions are of the utmost importance, particularly when recursion is involved! — Andrew D. King, Feb 05 '13 at 19:12
@Jernej: what do you mean by "subdivision" in "Sage simply computes the subdivision of the Laplacian matrix"? For non-empty graphs, one can remove an arbitrary row and column and compute the determinant. How does sage remove a row from the empty matrix. — Günter Rote, Feb 07 '13 at 14:15
By definition, an empty graph is a graph with no edges. An empty graph with $n$ vertices is a tree if $n=1$; it's not a tree if $n\gt1$. — bof, Mar 19 '22 at 08:14

score 53 · Accepted Answer · edited Mar 18 '22 at 13:24

53

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.

edited Mar 18 '22 at 13:24

The Amplitwist

1,446

answered Feb 01 '13 at 20:15

Sergey Norin

3,168

18

Yes, it's the union of zero trees. – David Roberts Feb 04 '13 at 04:03
43

... proving that it is possible to see the forest for the trees. – Terry Tao Feb 04 '13 at 18:56

score 25 · Answer 2 · edited Mar 18 '22 at 14:15

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.

score 18 · Answer 3 · answered Feb 02 '13 at 14:32

18

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.

answered Feb 02 '13 at 14:32

Andreas Blass

72,290

1

Then $2$, being equal to $(-1)\times (-2)$, is not prime? – ACL Feb 05 '13 at 00:57
3

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 05 '13 at 14:03
Understood. It was kind of a joke! I'm sorry. – ACL Feb 05 '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
4

@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 02:31

André Henriques · Answer 4 · 2014-01-28T03:46:56.850

14

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

edited Jan 28 '14 at 03:46

answered Feb 04 '13 at 23:26

André Henriques

42,480

5

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 05 '13 at 00:07
@ToddTrimble Is it 100% uncontroversial that an equivalence class has to be nonempty? If one defines an equivalence class as a maximal subset where any two points are in relation, it can be empty if the ambient set is empty. – user56097 Apr 17 '20 at 17:27
I usually see connectedness to be defined before the notion of connected components. And usually, for this original definition, empty spaces are indeed connected. But maybe this says more about the kind of maths books I read than about mathematics itself... :-/ – user56097 Apr 17 '20 at 17:30
If you want the quotient map from a set $X$ to the set of equivalence classes $X/E$ with respect to an equivalence relation $E$ to be a surjection (and I think theorems become more awkward if you don't), then yes, equivalence classes had better be nonempty. For example, if you want quotients and disjoint sums to get along properly, then it'd be a little weird to consider a disjoint sum of sets equipped with equivalence relations (inducing an equivalence relation on the whole), and then consider the case where a lot of those sets are empty. I feel confident my convention is "best practice". – Todd Trimble Apr 17 '20 at 17:55
Normally when people define partitions of a set, they mean a collection of disjoint nonempty subsets $X_1, X_2, \ldots$ that cover the set, as opposed to a situation where some of the partition classes are allowed to be empty (they'd still be disjoint, after all). And people want there to be a bijective correspondence between equivalence relations and partitions. That's another way to think of it. – Todd Trimble Apr 17 '20 at 18:02
How about the term "nondisconnected" to mean connected or empty? – PrimeRibeyeDeal Mar 19 '22 at 17:36

score 10 · Answer 5 · answered Feb 01 '13 at 21:30

10

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

answered Feb 01 '13 at 21:30

Fred Rohrer

6,670

8

and (consistently) in Bourbaki, the empty space is connected. – YCor Feb 01 '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 04 '13 at 03:40
2

I would say, that the one to blame are the same who say nonpositive for negative, and so on. – ACL Feb 04 '13 at 22:34
1

@ACL: As far as I know, Bourbaki does not use "nonpositive". – Fred Rohrer Feb 05 '13 at 06:11
2

@Fred: well observed :-) – ACL Feb 07 '13 at 22:22

score 8 · Answer 6 · edited Mar 18 '22 at 14:14

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)

Samuel Vidal · Answer 7 · 2013-02-01T21:16:05.893

4

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.

edited Feb 01 '13 at 21:16

answered Feb 01 '13 at 21:07

Samuel Vidal

244

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 01 '13 at 23:51
2

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 04 '13 at 18:41
1

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 05 '13 at 19:10
"disconnected" and "connected" not forming a dichotomy : brilliant, that's the point ! – Samuel Vidal Feb 09 '13 at 18:08

score 2 · Answer 8 · answered Feb 05 '13 at 08:05

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

Aaron Meyerowitz · Answer 9 · 2013-02-26T22:49:50.393

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.

Well of course a rooted tree can't be empty, because it has a root. — Todd Trimble, Feb 02 '13 at 13:57
All the definitions of rooted tree I've seen (except in your answer) stipulate a distinguished node called the root. — Todd Trimble, Feb 03 '13 at 05: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 03 '13 at 05: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 03 '13 at 16:23
In computer science, (ordered) binary trees are usually defined as a (least) fixed point of $1+T\times T=T$. The empty tree is a binary tree by definition. Binary trees seem to be rather different from connected acyclic graphs. — rgrig, Feb 28 '13 at 11:46

score 1 · Answer 10 · answered Mar 19 '22 at 03:19

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.

Is the empty graph a tree?

10 Answers10

Linked