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, ... (Sloane's 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.

CITE THIS AS:

Weisstein, Eric W. "Disconnected Graph." From MathWorld--A Wolfram Web Resource. http://mathworld.wolfram.com/DisconnectedGraph.html