A connected graph is an undirected graph in which any two distinct vertices are joined by a graph
path. Equivalently, the graph, viewed as a topological
space, is connected. An undirected graph
that is not connected is said to be disconnected.
This definition takes the null graph and singleton
graph to be connected, while empty graphs on 
vertices
are disconnected.
According to West (2001, p. 150), the singleton graph 
,
"is annoyingly inconsistent" since it is connected but for consistency
in discussing connectivity, it is considered to have vertex
connectivity 
.
If 
is the adjacency matrix of a finite simple graph 
, then entry 
of 
is the number of 
-walks from vertex 
to vertex 
. As a result, such a graph
on 
vertices is connected iff
 |
has no zero off-diagonal entries.
A finite connected simple graph on 
vertices satisfies
 |
where 
is the vertex degree of vertex 
. Equality holds iff
the graph is a tree. The inequality
is necessary but not sufficient
for a finite simple graph
to be connected.
A graph may be tested in the Wolfram Language to see if it is a connected graph using ConnectedGraphQ[g].
The numbers of connected unlabeled graphs on 
, 2, ... vertices
are 1, 1, 2, 6, 21, 112, 853, 11117, 261080, ... (OEIS A001349),
the first few of which are illustrated above.
The total numbers of unlabeled graphs on 
vertices,
not necessarily connected, are 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).
More generally, suppose a graph property holds iff
it holds for every connected component. If
counts connected unlabeled
graphs on 
vertices with that property, then its Euler
transform 
counts all unlabeled graphs with the property.
This application of the Euler transform is called
Riddell's formula.
The numbers of connected labeled graphs on 
vertices
are 1, 1, 4, 38, 728, 26704, ... (OEIS A001187),
and the total numbers of labeled graphs on
vertices,
not necessarily connected, are 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 
vertices 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.
If a simple graph 
is disconnected, then
its graph 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 graph complement.
A finite simple graph on more than 
vertices is k-connected
when its vertex connectivity satisfies 
, where 
is a positive integer.
Every such graph has minimum
vertex degree at least 
. In particular, 1-connected graphs are exactly the connected
graphs on at least two vertices.
For a finite connected simple graph on 
vertices, the maximum difference
between its edge count and vertex
count is 
,
attained by the complete graph 
.
