In mathematics and computer science, connectivity is one of the basic concepts of graph theory. It is closely related to the theory of network flow problems. The connectivity of a graph is an important measure of its robustness as a network.

Definitions of components, cuts and connectivity

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. A graph is called connected if every pair of vertices in the graph is connected. A connected component is a maximal connected subgraph of G. Each vertex belongs to exactly one connected component, as does each edge.

A directed graph is called weakly connected if replacing all of its directed edges with undirected edges produces a connected (undirected) graph. It is strongly connected or strong if it contains a directed path from u to v for every pair of vertices u,v. The strong components are the maximal connected subgraphs

A cut or vertex cut of a connected graph G is a set of vertices whose removal renders G disconnected. The connectivity or vertex connectivity κ(G) is the size of a smallest vertex cut. A graph is called k-connected or k-vertex-connected if its vertex connectivity is k or greater. A complete graph with n vertices has no cuts at all, but by convention its connectivity is 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; that is, κ(u,v)=κ(v,u). Moreover, κ(G) equals the minimum of κ(u,v) over all pairs of vertices u,v.

Analogous concepts can be defined for edges. Thus 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.

All of these definitions and notations carry over to directed graphs. Local connectivity and local edge-connectivity are not necessarily symmetric for directed graphs.

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 greatest number of independent paths between u and v is written as λ(u,v), and the greatest number of edge-independent paths between u and v is written as λ′(u,v).

Menger's theorem asserts that κ(u,v) = λ(u,v) and κ′(u,v) = λ′(u,v) for every pair of vertices u and v. 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, or to count the number of connected components.

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. Hence, directed graph connectivity may be solved in $O(\backslash log\; n)$ space.

Examples

• The vertex- and edge-connectivities of a disconnected graph are both 0.
• 1-connectedness is synonymous with connectedness.
• 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 every pair of vertices is 1.

Properties

• Connectedness is preserved by graph homomorphisms.
• If G is connected then its line graph L(G) is also connected.
• The vertex-connectivity of a graph is less than or equal to its edge-connectivity. That is, κ(G) ≤ κ′(G).
• If a graph G is k-connected, then for every set of vertices U of cardinality k, there exists a cycle in G containing U. The converse is true when k = 2.
• A graph G is 2-edge-connected if and only if it has an orientation that is strongly connected.

See also

• Algebraic connectivity

graph theory

Souvislý graf | Zusammenhang von Graphen | גרף קשיר | 連結グラフ | Graf spójny | Связный граф