Disconnected Graph


A graph G is said to be disconnected if it is not connected, i.e., if there exist two nodes in G such that no path in G has those nodes as endpoints. The numbers of disconnected simple unlabeled graphs on n=1, 2, ... nodes are 0, 1, 2, 5, 13, 44, 191, ... (OEIS A000719).

If G is disconnected, then its complement G^_ 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 C_5 which is connected and isomorphic to its complement.

See also

Connected Graph, k-Connected Graph, Minimum Vertex Cut

Explore with Wolfram|Alpha


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 p=18 Points." Report LA-3775. Los Alamos, NM: Los Alamos National Laboratory, Oct. 1967.

Referenced on Wolfram|Alpha

Disconnected Graph

Cite this as:

Weisstein, Eric W. "Disconnected Graph." From MathWorld--A Wolfram Web Resource.

Subject classifications