A connected graph is graph that is connected in the sense of a topological space, i.e., there is a path
from any point to any other point in the graph. A graph
that is not connected is said to be disconnected.
This definition means that the null graph and singleton
graph are considered connected, while empty graphs
on 
nodes are disconnected.
According to West (2001, p. 150), the singleton graph 
,
"is annoyingly inconsistent" since it is connected (specifically, 1-connected),
but for consistency in discussing connectivity, it is considered to have vertex
connectivity 
.
If 
is the adjacency matrix of a simple
graph 
,
then entry 
of 
is the number of 
-walks
from vertex 
to vertex 
.
As a result, a graph on 
nodes is connected iff
 |
has no matrix element equal to zero.
A connected graph on 
nodes satisfies
 |
where 
is the vertex degree of vertex 
(and where the inequality can be made strict except in the
case of the singleton graph 
). However while this condition is necessary
for a graph to be connected, it is not sufficient;
an arbitrary graph satisfying the above inequality may be connected or disconnected.
The number of 
-node
connected unlabeled graphs for 
, 2, ... are 1, 1, 2, 6, 21, 112, 853, 11117, 261080, ...
(OEIS A001349). The total number of
(not necessarily connected) unlabeled 
-node graphs is given by the Euler
transform of the preceding sequence, 1, 2, 4, 11, 34, 156, 1044, 12346, ... (OEIS
A000088; Sloane and Plouffe 1995, p. 20).
Furthermore, in general, if 
is the number of unlabeled connected graphs on 
nodes satisfying some property, then the Euler
transform 
is the total number of unlabeled graphs (connected or not) with the same property.
This application of the Euler transform is called
Riddell's formula.
The numbers of connected labeled graphs on 
-nodes are 1, 1, 4, 38, 728, 26704, ... (OEIS A001187),
and the total number of (not necessarily connected) labeled 
-node graphs is given by the exponential
transform of the preceding sequence: 1, 2, 8, 64, 1024, 32768, ... (OEIS A006125;
Sloane and Plouffe 1995, p. 19).
An efficient enumeration of connected graphs on 
nodes can be done using the program geng (part of
nauty) by B. McKay using the syntax geng -c n. However,
since the order in which graphs are returned by the geng program changes
as a function of time as improvements are made, the canonical ordering given on McKay's
website is used here and in GraphData.
A graph may be tested in the Wolfram Language to see if it is a connected graph using ConnectedGraphQ[g].
If 
is disconnected, then its complement 
is connected (Skiena 1990, p. 171; Bollobás
1998). However, the converse is not true, as can be seen using the example of the
cycle graph 
which is connected and isomorphic to its complement.
One can also speak of k-connected graphs (i.e., graphs with vertex connectivity 
) in which each vertex has degree at least
(i.e., the minimum of the degree
sequence is 
).
1-connected graphs are therefore connected with minimal degree 
.
