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.

Is the empty graph always connected ? I've looked through some sources (for example Diestels "Graph theory") and this special case seems to be ommited. What is the general opinion for this case ?

As I could gather from reading Diestel Graph theory, the disconnected graphs and the trivial graph (meaning the one with just one vertex) are 0-connected. But the trivial graph is connected, since there always is a path from that node to itself. So isn't the terminology a bit misleading ? Because one could take "0-connected" to mean "disconnected", but in the case of the trivial graph this doesn't hold anymore, which seems to me to be - at the level of terminology - unaesthetic.

share|improve this question
9  
"This is not Mathematics. This is Theology." –  Mark Jul 9 '11 at 23:08
    
If this is a quote, from whom is it ? Anyway, +1 :D –  resu Jul 10 '11 at 7:07
    
Paul Gordan, I believe, in regards to Hilbert's proof of the basis theorem. –  Mark Jul 14 '11 at 9:15

3 Answers 3

up vote 20 down vote accepted

My opinion is that the empty graph ought to be regarded as disconnected, in the same way that $1$ ought to be regarded as not prime. The reason is that every graph should have a unique "prime factorization" into a disjoint union of connected graphs, and this theorem is false if you allow the empty graph to be connected.

The fact that the standard definition ("any two vertices can be connected by a path") is vacuously true for the empty graph is misleading. This is a phenomenon known on the nLab as too simple to be simple and it is caused by using definitions which don't work well for empty objects. Here is a better definition:

A graph is connected if it has exactly one connected component.

Recall that a connected component is an equivalence class under the equivalence relation generated by the relation of adjacency; in particular I do not need to define the word "connected" to define what a connected component is. The empty graph has zero, rather than one, connected components.

share|improve this answer
    
Could you define a little bit more explicit, what you mean by "the equivalence relation generated by the relation of adjacency" ? In the absence of more information I took you meant the adjacency relation was something like this mathworld.wolfram.com/AdjacencyRelation.html. If one defines an (equivalence?) relation on top of that (2 vertices are equivalent, if there are vertices such that one can form pairs of vertices that are adjacent to another and lead from one of those 2 vertices to the other), is this relation even reflexive ? –  resu Jul 10 '11 at 7:19
1  
@resu: I expect Qiaochu is taking the reflexive transitive closure of the adjacency relation, so the new relation is reflexive by fiat. –  Miha Habič Jul 10 '11 at 8:27
    
Ok, that seems to make sense. But (@Qiaochu) how about my side question about the connectivity: $K^1$ is 0-connected, like the disconnected graphs, but it is connected. Isn't this a weird terminological choice, since one would expect only the disconnected graphs to be 0-connected ? –  resu Jul 10 '11 at 9:10
    
@resu: I don't have a good intuition about $k$-connectivity so I don't have a strong opinion about how it should degenerate. –  Qiaochu Yuan Jul 10 '11 at 13:54
    
Terrific analogy between the empty graph and the role of 1 in prime factorization. The same analogy (and all that is holy!) suggests the empty graph isn't disconnected, either, just as 1 is not considered composite. Surely disconnected implies at least two pieces. (re: "My opinion is that the empty graph ought to be regarded as disconnected.") –  I. J. Kennedy Aug 26 '13 at 15:01

For some authors, empty graphs and null graphs are different concepts. The null graph is the graph without nodes, while an empty graph is a graph without edges. An empty graph of two vertices is not connected.

Regarding the null graph, it of course depends on the definition of connectivity. If a graph is connected if any two vertices can be connected by a path, then the null graph is connected.

share|improve this answer

A graph is connected if for all $x, y \in V(G)$ there exists a path from $x$ to $y$ using edges in $E(G)$. The null graph satisfies that criteria so it is connected. The term disconnected is the negation of connected; that is, there exists an $x, y \in V(G)$ for which there is no path from $x$ to $y$ using edges in $E(G)$. It is impossible to find such an $x$ and $y$ because the set is empty, therefore, the null graph cannot be disconnected.

We aren't allowed to change the standard definition to "A graph is connected if it has exactly one connected component". Moreover, it makes no sense to define "connected" using the term "connected component" because in order to talk about a connected component you'd already have to know what connected meant (as well as the term "component").

On a personal level, the definition of graph that I learned did not allow for the null graph. A graph consisted of a nonempty set V of vertices together with a (possibly empty) set of edges, E. It would seem prudent to define "graph" this way to keep the null graph from existing.

share|improve this answer
2  
As I described in my answer, you do not need to define "connected" to define "connected component." There are various things that are called graphs and various definitions that one might want of basic properties of such things. Definitions are not set in stone: they are there for reasons, and some of those reasons are not good reasons. You will also note that I prefaced my answer with "in my opinion" because I recognize that my position is not universal. –  Qiaochu Yuan Jul 14 '11 at 1:35
    
Here is an example of a similar definition which doesn't work the way it should: "a natural number $p$ is prime if it has no divisors other than $1$ and $p$." Using this definition $1$ is prime, and now we don't have unique prime factorization. Silly, right? A better definition is "a natural number $p$ is prime if it has exactly two divisors." –  Qiaochu Yuan Jul 14 '11 at 1:40
    
A "red car" is a "car" that is "red". To talk about a "connected component" you need to know what is meant by "connected" and "component". But you've defined something as "connected" by being a "connected component". That's backwards. –  DJP Jul 14 '11 at 2:17
1  
@DJP: if you can read Qiaochu's definition, you'll see it is not circular. Your linguistic argument is at best an argument for how things should be named. But (and, if it helps, I agree that this is somewhat unfortunate) this sort of thing is common in mathematics: e.g. one does not need to know what Lebesgue measure is in order to define "measure zero". If it makes you feel better, pretend that Qiaochu defined the components of a graph instead... –  Pete L. Clark Jul 14 '11 at 3:03
1  
In mathematics, a red herring is neither necessarily red nor necessarily a fish. –  JeffE Oct 11 '11 at 12:42

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.