Connected Graph
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 
.
Contact the MathWorld Team
connected graph
