A connected graph is graph that is connected in the sense of a topological space, i.e., there is a path from any point to any other point in the graph. A graph that is not connected is said to be disconnected. This definition means that the null graph and singleton graph are considered connected, while empty graphs on nodes are disconnected.
According to West (2001, p. 150), the singleton graph , "is annoyingly inconsistent" since it is connected (specifically, 1-connected), but for consistency in discussing connectivity, it is considered to have vertex connectivity .
If is the adjacency matrix of a simple graph , then entry of is the number of -walks from vertex to vertex . As a result, a graph on nodes is connected iff
has no matrix element equal to zero.
A connected graph on nodes satisfies
where is the vertex degree of vertex (and where the inequality can be made strict except in the case of the singleton graph ). However while this condition is necessary for a graph to be connected, it is not sufficient; an arbitrary graph satisfying the above inequality may be connected or disconnected.
The number of -node connected unlabeled graphs for , 2, ... are 1, 1, 2, 6, 21, 112, 853, 11117, 261080, ... (OEIS A001349). The total number of (not necessarily connected) unlabeled -node graphs is given by the Euler transform of the preceding sequence, 1, 2, 4, 11, 34, 156, 1044, 12346, ... (OEIS A000088; Sloane and Plouffe 1995, p. 20). Furthermore, in general, if is the number of unlabeled connected graphs on nodes satisfying some property, then the Euler transform is the total number of unlabeled graphs (connected or not) with the same property. This application of the Euler transform is called Riddell's formula.
The numbers of connected labeled graphs on -nodes are 1, 1, 4, 38, 728, 26704, ... (OEIS A001187), and the total number of (not necessarily connected) labeled -node graphs is given by the exponential transform of the preceding sequence: 1, 2, 8, 64, 1024, 32768, ... (OEIS A006125; Sloane and Plouffe 1995, p. 19).
An efficient enumeration of connected graphs on nodes can be done using the program geng (part of nauty) by B. McKay using the syntax geng -c n. However, since the order in which graphs are returned by the geng program changes as a function of time as improvements are made, the canonical ordering given on McKay's website is used here and in GraphData.
A graph may be tested in the Wolfram Language to see if it is a connected graph using ConnectedGraphQ[g].
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.
One can also speak of k-connected graphs (i.e., graphs with vertex connectivity ) in which each vertex has degree at least (i.e., the minimum of the degree sequence is ). 1-connected graphs are therefore connected with minimal degree .