Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question

1 Answer 1

up vote 13 down vote accepted

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.

share|improve this answer
1  
@Qiaochu I agree completely... If you can have concepts like (-1)-coloring of graphs, then you should be able to have the concept of a null-graph. Math is the study of the abstract, and null-graphs definitely fall into that category. –  Nicolas Villanueva Jun 8 '11 at 13:26
1  
Isn't the connectivity of a graph defined in terms of there being a path between any pair of vertices? By this definition, the null graph is connected. Perhaps the paradoxical property is that the null graph is the only connected graph which does not have one connected component. –  Rahul Jun 8 '11 at 13:51
3  
@Rahul: no. The empty graph is not connected for the same reason that $1$ is not prime: because you want a graph to have a unique decomposition into connected components, and uniqueness is impossible if you call the empty graph connected. (From the perspective of the nLab article the correct definition is "there exists a path between any pair of vertices, and there exists at least one such pair.") –  Qiaochu Yuan Jun 8 '11 at 14:17
1  
@Qiaochu: well, I'm thinking about it. For one thing, I want $\operatorname{Spec} R$ to be connected iff $R$ has no nontrivial idempotents, but I know what you're going to say: we should distinguish between rings which have $2$ idempotents and rings which have only $1$ idempotent! Also: the definition of connectedness via continuous functions to $\{0,1\}$ makes the empty space connected (although again you could redefine a "constant function" here). I also want arbitrary products of connected spaces to be connected... –  Pete L. Clark Jun 8 '11 at 14:31
1  
@Pete: arbitrary products of connected spaces are connected either way! I'm not sure what you mean by the definition of connectedness via continuous functions to $\{ 0, 1 \}$, but this is the same issue as the idempotents: you want there to be no non-constant functions, as well as two trivial constant functions (another example of the nLab's "existence and uniqueness" observation). –  Qiaochu Yuan Jun 8 '11 at 14:44

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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