A graph
is said to be disconnected if it 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.
is said to be disconnected if it 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.