A disconnected graph is a graph that is not connected,
i.e., if there exist two nodes in such that no path in has those nodes as endpoints.
The numbers of disconnected simple unlabeled graphs
on ,
2, ... nodes are 0, 1, 2, 5, 13, 44, 191, ... (OEIS
A000719).
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.
Bollobás, B. Modern Graph Theory. New York: Springer-Verlag, 1998.Harary, F. "The
Number of Linear, Directed, Rooted, and Connected Graphs." Trans. Amer. Math.
Soc.78, 445-463, 1955.Read, R. C. and Wilson, R. J.
An
Atlas of Graphs. Oxford, England: Oxford University Press, 1998.Skiena,
S. Implementing
Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading,
MA: Addison-Wesley, 1990.Sloane, N. J. A. Sequence A000719/M1452
in "The On-Line Encyclopedia of Integer Sequences."Stein,
M. L. and Stein, P. R. "Enumeration of Linear Graphs and Connected
Linear Graphs up to
Points." Report LA-3775. Los Alamos, NM: Los Alamos National Laboratory, Oct. 1967.
that is not connected,
i.e., if there exist two nodes in 
such that no path in 
has those nodes as endpoints.
The numbers of disconnected simple unlabeled graphs
on 
,
2, ... nodes are 0, 1, 2, 5, 13, 44, 191, ... (OEIS
A000719).
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.
Points." Report LA-3775. Los Alamos, NM: Los Alamos National Laboratory, Oct. 1967.