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.
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.
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.