Skip to main content
Source Link
Jernej
  • 3.5k
  • 1
  • 27
  • 41

Is the empty graph a tree?

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?