Connectivity (graph theory)

File:Network Community Structure.svg

This graph becomes disconnected when the right-most node in the gray area on the left is removed

File:Sample-graph.jpg

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

File:UndirectedDegrees.svg

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

In an undirected graph Template:Mvar, two vertices Template:Mvar and Template:Mvar are called connected if Template:Mvar contains a path from Template:Mvar to Template:Mvar. 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 Template:Mvar is therefore disconnected if there exist two vertices in Template:Mvar such that no path in Template:Mvar 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 Template:Mvar to Template:Mvar or a directed path from Template:Mvar to Template:Mvar for every pair of vertices u, v. It is strongly connected, or simply strong, if it contains a directed path from Template:Mvar to Template:Mvar and a directed path from Template:Mvar to Template:Mvar 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 Template:Mvar is a set of vertices whose removal renders Template:Mvar disconnected. The vertex connectivity κ(G) (where Template:Mvar is not a complete graph) is the size of a smallest vertex cut. A graph is called Template:Mvar-vertex-connected or Template:Mvar-connected if its vertex connectivity is Template:Mvar or greater.

More precisely, any graph Template:Mvar (complete or not) is said to be Template:Mvar-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 Template:Mvar such that Template:Mvar is Template:Mvar-connected. In particular, a complete graph with Template:Mvar vertices, denoted Template:Mvar, has no vertex cuts at all, but κ(K_n) = n − 1.

A vertex cut for two vertices Template:Mvar and Template:Mvar is a set of vertices whose removal from the graph disconnects Template:Mvar and Template:Mvar. The local connectivity κ(u, v) is the size of a smallest vertex cut separating Template:Mvar and Template:Mvar. 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 Template:Mvar 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 Template:Mvar 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 Template:Mvar from Template:Mvar. Again, local edge-connectivity is symmetric. A graph is called Template:Mvar-edge-connected if its edge connectivity is Template:Mvar 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.

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.

More precisely: a Template:Mvar 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 Template:Mvar 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.

A cutset Template:Mvar of Template:Mvar is called a non-trivial cutset if Template:Mvar does not contain the neighborhood N(u) of any vertex u ∉ X. Then the superconnectivity ${\kappa }_1$ of Template:Mvar is $${\kappa }_1(G)=\min \{|X|:X\text{ is a non-trivial cutset}\}.$$

A non-trivial edge-cut and the edge-superconnectivity ${\lambda }_1(G)$ are defined analogously.

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 Template:Mvar and Template:Mvar are vertices of a graph Template:Mvar, then a collection of paths between Template:Mvar and Template:Mvar is called independent if no two of them share a vertex (other than Template:Mvar and Template:Mvar themselves). Similarly, the collection is edge-independent if no two paths in it share an edge. The number of mutually independent paths between Template:Mvar and Template:Mvar is written as κ′(u, v), and the number of mutually edge-independent paths between Template:Mvar and Template:Mvar 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). 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:

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

By Menger's theorem, for any two vertices Template:Mvar and Template:Mvar in a connected graph Template:Mvar, the numbers κ(u, v) and λ(u, v) can be determined efficiently using the max-flow min-cut algorithm. The connectivity and edge-connectivity of Template:Mvar 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, 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.

Number of connected graphs

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

File:The number of connected graphs with 4 vertices.png

The number and images of connected graphs with 4 nodes

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 two vertices.
• The complete graph on Template:Mvar vertices has edge-connectivity equal to n − 1. Every other simple graph on Template:Mvar 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) ≤ λ(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.
• For a vertex-transitive graph of degree Template:Mvar, we have: 2(d + 1)/3 ≤ κ(G) ≤ λ(G) = d.
• For a vertex-transitive graph of degree d ≤ 4, or for any (undirected) minimal Cayley graph of degree Template:Mvar, or for any symmetric graph of degree Template:Mvar, both kinds of connectivity are equal: κ(G) = λ(G) = d.

Other properties

• Connectedness is preserved by graph homomorphisms.
• If Template:Mvar is connected then its line graph L(G) is also connected.
• A graph Template:Mvar 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 Template:Mvar-dimensional convex polytope is a Template:Mvar-vertex-connected graph. Steinitz's previous theorem that any 3-vertex-connected planar graph is a polytopal graph (Steinitz's theorem) gives a partial converse.
• According to a theorem of G. A. Dirac, if a graph is Template:Mvar-connected for k ≥ 2, then for every set of Template:Mvar vertices in the graph there is a cycle that passes through all the vertices in the set. The converse is true when k = 2.

See also

• Algebraic connectivity
• Cheeger constant (graph theory)
• Dynamic connectivity, Disjoint-set data structure
• Expander graph
• Strength of a graph