This graph becomes disconnected when the dashed edge is removed.

In mathematics and computer science, connectivity is one of the basic concepts of graph theory: it asks for the minimum number of elements (nodes or edges) that need to be removed to separate the remaining nodes into two or more isolated subgraphs.^[1] It is closely related to the theory of network flow problems. The connectivity of a graph is an important measure of its resilience as a network.

Connected vertices and graphs

With vertex 0, this graph is disconnected. The rest of the graph is connected.

In an undirected graph $G$ , two vertices $u$ and $v$ are called connected if $G$ contains a path from $u$ to $v$ . Otherwise, they are called disconnected. If the two vertices are additionally connected by a path of length $1$ (that is, they are the endpoints of a single edge), the vertices are called adjacent.

A graph is said to be connected if every pair of vertices in the graph is connected. This means that there is a path between every pair of vertices. An undirected graph that is not connected is called disconnected. An undirected graph G is therefore disconnected if there exist two vertices in G such that no path in G has these vertices as endpoints. A graph with just one vertex is connected. An edgeless graph with two or more vertices is disconnected.

A directed graph is called weakly connected if replacing all of its directed edges with undirected edges produces a connected (undirected) graph. It is unilaterally connected or unilateral (also called semiconnected) if it contains a directed path from $u$ to $v$ or a directed path from $v$ to $u$ for every pair of vertices $u, v$ .^[2] It is strongly connected, or simply strong, if it contains a directed path from $u$ to $v$ and a directed path from $v$ to $u$ for every pair of vertices $u, v$ .

Components and cuts

A connected component is a maximal connected subgraph of an undirected graph. Each vertex belongs to exactly one connected component, as does each edge. A graph is connected if and only if it has exactly one connected component.

The strong components are the maximal strongly connected subgraphs of a directed graph.

A vertex cut or separating set of a connected graph $G$ is a set of vertices whose removal renders $G$ disconnected. The vertex connectivity $κ (G)$ (where $G$ is not a complete graph) is the size of a minimal vertex cut. A graph is called $k$ -vertex-connected or $k$ -connected if its vertex connectivity is $k$ or greater.

More precisely, any graph $G$ (complete or not) is said to be $k$ -vertex-connected if it contains at least $k +1$ vertices, but does not contain a set of $k - 1$ vertices whose removal disconnects the graph; and $κ (G)$ is defined as the largest $k$ such that $G$ is $k$ -connected. In particular, a complete graph with $n$ vertices, denoted $K n$ , has no vertex cuts at all, but $κ (K n) = n - 1$ .

A vertex cut for two vertices $u$ and $v$ is a set of vertices whose removal from the graph disconnects $u$ and $v$ . The local connectivity $κ (u, v)$ is the size of a smallest vertex cut separating $u$ and $v$ . Local connectivity is symmetric for undirected graphs; that is, $κ (u, v) = κ (v, u)$ . Moreover, except for complete graphs, $κ (G)$ equals the minimum of $κ (u, v)$ over all nonadjacent pairs of vertices $u, v$ .

$2$ -connectivity is also called biconnectivity and $3$ -connectivity is also called triconnectivity. A graph $G$ which is connected but not $2$ -connected is sometimes called separable.

Analogous concepts can be defined for edges. In the simple case in which cutting a single, specific edge would disconnect the graph, that edge is called a bridge. More generally, an edge cut of $G$ is a set of edges whose removal renders the graph disconnected. The edge-connectivity $λ (G)$ is the size of a smallest edge cut, and the local edge-connectivity $λ (u, v)$ of two vertices $u, v$ is the size of a smallest edge cut disconnecting $u$ from $v$ . Again, local edge-connectivity is symmetric. A graph is called $k$ -edge-connected if its edge connectivity is $k$ or greater.

A graph is said to be maximally connected if its connectivity equals its minimum degree. A graph is said to be maximally edge-connected if its edge-connectivity equals its minimum degree.^[3]

Super- and hyper-connectivity

A graph is said to be super-connected or super-κ if every minimum vertex cut isolates a vertex. A graph is said to be hyper-connected or hyper-κ if the deletion of each minimum vertex cut creates exactly two components, one of which is an isolated vertex. A graph is semi-hyper-connected or semi-hyper-κ if any minimum vertex cut separates the graph into exactly two components.^[4]

More precisely: a $G$ connected graph is said to be super-connected or super-κ if all minimum vertex-cuts consist of the vertices adjacent with one (minimum-degree) vertex. A $G$ connected graph is said to be super-edge-connected or super-λ if all minimum edge-cuts consist of the edges incident on some (minimum-degree) vertex.^[5]

A cutset $X$ of $G$ is called a non-trivial cutset if $X$ does not contain the neighborhood $N(u)$ of any vertex $u \notin X$ . Then the superconnectivity κ1 of G is:

κ1(G) = min{|X| : X is a non-trivial cutset}.

A non-trivial edge-cut and the edge-superconnectivity λ1(G) are defined analogously.^[6]

Menger's theorem

Main article: Menger's theorem

One of the most important facts about connectivity in graphs is Menger's theorem, which characterizes the connectivity and edge-connectivity of a graph in terms of the number of independent paths between vertices.

If $u$ and $v$ are vertices of a graph $G$ , then a collection of paths between $u$ and $v$ is called independent if no two of them share a vertex (other than $u$ and $v$ themselves). Similarly, the collection is edge-independent if no two paths in it share an edge. The number of mutually independent paths between $u$ and $v$ is written as $κ' (u, v)$ , and the number of mutually edge-independent paths between $u$ and $v$ is written as $λ' (u, v)$ .

Menger's theorem asserts that for distinct vertices u,v, $λ (u, v)$ equals $λ' (u, v)$ , and if u is also not adjacent to v then $κ (u, v)$ equals $κ' (u, v)$ .^[7]^[8] This fact is actually a special case of the max-flow min-cut theorem.

Computational aspects

The problem of determining whether two vertices in a graph are connected can be solved efficiently using a search algorithm, such as breadth-first search. More generally, it is easy to determine computationally whether a graph is connected (for example, by using a disjoint-set data structure), or to count the number of connected components. A simple algorithm might be written in pseudo-code as follows:

Begin at any arbitrary node of the graph, $G$
Proceed from that node using either depth-first or breadth-first search, counting all nodes reached.
Once the graph has been entirely traversed, if the number of nodes counted is equal to the number of nodes of $G$ , the graph is connected; otherwise it is disconnected.

By Menger's theorem, for any two vertices $u$ and $v$ in a connected graph $G$ , the numbers $κ (u, v)$ and $λ (u, v)$ can be determined efficiently using the max-flow min-cut algorithm. The connectivity and edge-connectivity of $G$ can then be computed as the minimum values of $κ (u, v)$ and $λ (u, v)$ , respectively.

In computational complexity theory, SL is the class of problems log-space reducible to the problem of determining whether two vertices in a graph are connected, which was proved to be equal to L by Omer Reingold in 2004.^[9] Hence, undirected graph connectivity may be solved in $O(log n)$ space.

The problem of computing the probability that a Bernoulli random graph is connected is called network reliability and the problem of computing whether two given vertices are connected the ST-reliability problem. Both of these are #P-hard.^[10]

Number of connected graphs

Main article: Graph enumeration

The number of distinct connected labeled graphs with n nodes is tabulated in the On-Line Encyclopedia of Integer Sequences as sequence A001187. The first few non-trivial terms are

n	graphs
1	1
2	1
3	4
4	38
5	728
6	26704
7	1866256
8	251548592

Examples

The vertex- and edge-connectivities of a disconnected graph are both $0$ .
$1$ -connectedness is equivalent to connectedness for graphs of at least 2 vertices.
The complete graph on $n$ vertices has edge-connectivity equal to $n - 1$ . Every other simple graph on $n$ vertices has strictly smaller edge-connectivity.
In a tree, the local edge-connectivity between any two distinct vertices is $1$ .

Bounds on connectivity

The vertex-connectivity of a graph is less than or equal to its edge-connectivity. That is, $κ (G) \leq λ (G)$ .
The edge-connectivity for a graph with at least 2 vertices is less than or equal to the minimum degree of the graph because removing all the edges that are incident to a vertex of minimum degree will disconnect that vertex from the rest of the graph.^[1]
For a vertex-transitive graph of degree $d$ , we have: $2(d + 1)/3 \leq κ (G) \leq λ (G) = d$ .^[11]
For a vertex-transitive graph of degree $d \leq 4$ , or for any (undirected) minimal Cayley graph of degree $d$ , or for any symmetric graph of degree $d$ , both kinds of connectivity are equal: $κ (G) = λ (G) = d$ .^[12]

Other properties

Connectedness is preserved by graph homomorphisms.
If $G$ is connected then its line graph $L (G)$ is also connected.
A graph $G$ is $2$ -edge-connected if and only if it has an orientation that is strongly connected.
Balinski's theorem states that the polytopal graph ( $1$ -skeleton) of a $k$ -dimensional convex polytope is a $k$ -vertex-connected graph.^[13] Steinitz's previous theorem that any 3-vertex-connected planar graph is a polytopal graph (Steinitz theorem) gives a partial converse.
According to a theorem of G. A. Dirac, if a graph is $k$ -connected for $k \geq 2$ , then for every set of $k$ vertices in the graph there is a cycle that passes through all the vertices in the set.^[14]^[15] The converse is true when $k = 2$ .