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. 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.

connected graph | k-connected graph | minimum vertex cut