# Is the empty graph connected?

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.

• "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
• Please define your terms; this is hopelessly confusing. Some people use "Empty graph" to mean a graph with no edges that may still have nodes. You've said "the trivial graph" is the one with just one vertex, but it's not clear whether you're intending "empty graph" to mean the same thing as "trivial graph" in that sense. – Don Hatch Nov 30 '17 at 1:42

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.

• 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
• @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
• 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
• Meanwhile, there is the generalized equation for planar graphs $v-e+f=c+1$, where $c$ is the number of components. The empty graph obeys this, and the usual inductive proofs on the size of the planar graph work just as well for this as they do in the special case of connected graphs---I would say it is even easier, since you can add all the vertices as separate components first, and then add the edges one-by-one. Are there issues with your triangulation formalization when $c>1$? – JDH Jul 4 '14 at 11:48
• It would help to mention that you're taking "empty graph" to mean no vertices. That's not universally understood (e.g. see en.wiktionary.org/wiki/empty_graph), and not at all clear in the question either. – Don Hatch Nov 30 '17 at 1:44

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.

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.

• 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
• No, you don't. "Connected component" is just a series of characters that I defined to have a particular meaning. The fact that there's a space in it is irrelevant: I only use this term because it is recognizable terminology, but there is a way to get the same semantic concept via an alternate definition that doesn't proceed by first defining the word "connected." As long as I get a satisfactory end concept, it doesn't matter what path I used to get there. – Qiaochu Yuan Jul 14 '11 at 2:28
• @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
• In mathematics, a red herring is neither necessarily red nor necessarily a fish. – JeffE Oct 11 '11 at 12:42