Inmathematics 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.
In an undirected graph G, two vertices u and v are called connectedifG contains a path from utov. 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.
Agraph 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.
Adirected 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 utov or a directed path from vtou for every pair of vertices u, v.[2] It is strongly connected, or simply strong, if it contains a directed path from utov and a directed path from vtou for every pair of vertices u, v.
Aconnected 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.
Avertex cutorseparating 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-connectedork-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 Gisk-connected. In particular, a complete graph with n vertices, denoted Kn, has no vertex cuts at all, but κ(Kn) = n − 1.
Avertex 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]
A graph is said to be super-connectedorsuper-κ if every minimum vertex cut isolates a vertex. A graph is said to be hyper-connectedorhyper-κ if the deletion of each minimum vertex cut creates exactly two components, one of which is an isolated vertex. A graph is semi-hyper-connectedorsemi-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-connectedorsuper-κ 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-connectedorsuper-λ if all minimum edge-cuts consist of the edges incident on some (minimum-degree) vertex.[5]
A cutset XofG is called a non-trivial cutset if X does not contain the neighborhood N(u) of any vertex u ∉ X. Then the superconnectivity 
A non-trivial edge-cut and the edge-superconnectivity 
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.
Ifu 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.
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:
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.
Incomputational 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 LbyOmer 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]
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 |
