11
$\begingroup$

Standard definition of graph says that it is an ordered pair G=(N,L) where N is set of nodes and L is set of lines which connect the nodes.

From what I've read, the set L can be empty, but can set N be empty too?

I'm mainly asking this because for my exam, I found numerous problems that go like this: Graph X is given. How many subgraphs with property Y exist? Often the number depends on the definition of graph.

1 Answers 1

20

Depends on your definition of a graph. This is addressed in a paper of Harary, Is the null-graph a pointless concept? The abstract is as follows:

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.

Personally, I think there's no reason not to admit it as a graph. There is a philosophy due to Grothendieck that it's better to work in a nice category with nasty objects than in a nasty category with nice objects, and the null graph makes the category of graphs nicer (giving it an initial object). As for the paradoxical properties, I haven't read the paper but they are likely due to the phenomenon that the nLab calls too simple to be simple. For example, the empty graph is not connected; it has zero connected components instead of one.

  • 0
    @Rahul: hmm. I may have to retract my previous statement. I guess what I meant is "connected planar graph" turns out to be equivalent to "cell decomposition of the sphere" if the empty graph is not connected, and I guess "planar graph" is probably better off with its usual meaning.2011-06-08