3
$\begingroup$

For the following $2$ cases:

(1) $V = \emptyset, E = \emptyset $ (i.e. nothing at all)

(2) $V = \{v_0\}, E = \emptyset $ (i.e. only 1 root node $v_0$)

Are they considered a valid tree? It seems like different literature have different definitions.

I recall that I have read a data structures and algorithms book that defines "A tree is a set of nodes that either: is empty or has a designated node, called the root ...". According to this definition, (1) and (2) are both valid trees. I don't have the book on hand, but I am sure if you search the quoted sentence above in Google, you can get lots of results, as quite a lot of lecture notes follow this definition.

However, another definition of trees often met is defined in terms of graphs:

A tree is "a connected graph without a cycle".

Using this definition, my question is transformed to another question: "Is an empty graph a connected graph?" But the answer to the latter question is debatable according to here:

Is the empty graph connected?

My question is, which one is the more accepted definition?

$\endgroup$
5
$\begingroup$

Here are a few properties of trees which can be relevant:

  1. A tree on $n$ vertices has $n-1$ edges. Works for (2) but not for (1).

  2. A graph has no cycles iff it is a disjoint union of trees. Works for both (1) and (2), unless you require the decomposition into trees to be unique, in which case it works for (2) but not for (1).

  3. A tree is either a single vertex or a bunch of disjoint trees connected to a common vertex. Works for (2) but not for (1).

These examples suggest that the commonsense definition of tree should include (2) but not (1). Indeed, oftentimes it seems that the graph on no vertices is a pointless concept; see the classical discussion of Harary and Read, who present arguments for both sides of the issue.

Practically speaking, you should probably assume that (1) is not a legal graph, unless it makes sense in your application, and then you should explicitly mention the fact.

$\endgroup$
  • $\begingroup$ Of course, all properties you state can be made "safe" by saying "a non-empty graph". $\endgroup$ – Raphael Mar 11 '15 at 18:15
  • $\begingroup$ Related to the notion of (1) not being a legal graph: en.wikipedia.org/wiki/Null_graph $\endgroup$ – Klaus Draeger Mar 11 '15 at 18:29
  • 2
    $\begingroup$ Indeed, a "tree" with zero vertices is actually a forest with zero components: each forest with $k$ components and $n$ nodes has $n-k$ edges. $\endgroup$ – Hendrik Jan Mar 11 '15 at 23:50
  • 3
    $\begingroup$ I think the abstract from Harary and Read, particularly the last line, sums it up nicely: "The graph with no points and no lines is discussed critically. Arguments for and against its official admittance as a graph are presented. This is accompanied by an extensive survey of the literature. Paradoxical properties of the null-graph are noted. No conclusion is reached." $\endgroup$ – Luke Mathieson Mar 12 '15 at 0:40

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.