33
$\begingroup$

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?

$\endgroup$
24
  • 50
    $\begingroup$ A connected space should always be assumed to be non-empty, for the same reason that 1 is not considered to be a prime. $\endgroup$
    – Angelo
    Feb 1, 2013 at 19:52
  • 7
    $\begingroup$ 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. $\endgroup$ Feb 1, 2013 at 20:41
  • 52
    $\begingroup$ Is the empty graph a tree? No, but it's a forest. $\endgroup$ Feb 1, 2013 at 20:55
  • 18
    $\begingroup$ 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. $\endgroup$
    – Terry Tao
    Feb 2, 2013 at 6:08
  • 8
    $\begingroup$ If a tree falls in a forest and no one is around to notice, could it be empty? $\endgroup$
    – Todd Trimble
    Feb 2, 2013 at 14:00

10 Answers 10

52
$\begingroup$

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.

$\endgroup$
2
  • 17
    $\begingroup$ Yes, it's the union of zero trees. $\endgroup$ Feb 4, 2013 at 4:03
  • 42
    $\begingroup$ ... proving that it is possible to see the forest for the trees. $\endgroup$
    – Terry Tao
    Feb 4, 2013 at 18:56
26
$\begingroup$

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.

$\endgroup$
16
$\begingroup$

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.

$\endgroup$
5
  • 1
    $\begingroup$ Then $2$, being equal to $(-1)\times (-2)$, is not prime? $\endgroup$
    – ACL
    Feb 5, 2013 at 0:57
  • 3
    $\begingroup$ 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. $\endgroup$ Feb 5, 2013 at 14:03
  • $\begingroup$ Understood. It was kind of a joke! I'm sorry. $\endgroup$
    – ACL
    Feb 5, 2013 at 21:28
  • $\begingroup$ Isn't the empty graph the disjoint union of any family (of any cardinality) of empty graphs? $\endgroup$ Feb 26, 2013 at 23:09
  • 4
    $\begingroup$ @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). $\endgroup$ Feb 27, 2013 at 2:31
14
$\begingroup$

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

$\endgroup$
6
  • 5
    $\begingroup$ 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... $\endgroup$
    – Todd Trimble
    Feb 5, 2013 at 0:07
  • $\begingroup$ @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. $\endgroup$
    – user56097
    Apr 17, 2020 at 17:27
  • $\begingroup$ 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... :-/ $\endgroup$
    – user56097
    Apr 17, 2020 at 17:30
  • $\begingroup$ 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". $\endgroup$
    – Todd Trimble
    Apr 17, 2020 at 17:55
  • $\begingroup$ 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. $\endgroup$
    – Todd Trimble
    Apr 17, 2020 at 18:02
10
$\begingroup$

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

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

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)

$\endgroup$
4
$\begingroup$

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.

$\endgroup$
4
  • 5
    $\begingroup$ 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. $\endgroup$ Feb 1, 2013 at 23:51
  • 1
    $\begingroup$ 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)). $\endgroup$
    – Terry Tao
    Feb 4, 2013 at 18:41
  • 1
    $\begingroup$ 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". $\endgroup$ Feb 5, 2013 at 19:10
  • $\begingroup$ "disconnected" and "connected" not forming a dichotomy : brilliant, that's the point ! $\endgroup$ Feb 9, 2013 at 18:08
2
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
6
  • 9
    $\begingroup$ Well of course a rooted tree can't be empty, because it has a root. $\endgroup$
    – Todd Trimble
    Feb 2, 2013 at 13:57
  • $\begingroup$ Todd, that only holds if it has vertices! $\endgroup$ Feb 3, 2013 at 3:43
  • 3
    $\begingroup$ All the definitions of rooted tree I've seen (except in your answer) stipulate a distinguished node called the root. $\endgroup$
    – Todd Trimble
    Feb 3, 2013 at 5:17
  • $\begingroup$ 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. $\endgroup$ Feb 3, 2013 at 5:52
  • $\begingroup$ 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. $\endgroup$ Feb 3, 2013 at 16:23
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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