Connectivity (graph theory)
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. In an undirected graph , two "vertices" and are called connected if contains a path from to . Otherwise, they are called disconnected. If the two vertices  are additionally connected by a path of length , i.e. by 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 to or a directed path from to for every pair of vertices . It is strongly connected, or simply strong, if it contains a directed path from to and a directed path from to for every pair of vertices . 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 is a set of vertices whose removal renders disconnected. The vertex connectivity (where is not a complete graph) is the size of a minimal vertex cut. A graph is called "-vertex-connected or "-connected if its vertex connectivity is or greater. More precisely, any graph (complete or not) is said to be "-vertex-connected" if it contains at least vertices , but does not contain a set of vertices whose removal disconnects the graph; and is defined as the largest such that is -connected. In particular, a complete graph with vertices, denoted , has no vertex cuts at all, but . A vertex cut for two vertices and is a set of vertices whose removal from the graph disconnects and . The local connectivity is the size of a smallest vertex cut separating and . Local connectivity is symmetric for undirected graphs; that is, . Moreover, except for complete graphs, equals the minimum of over all nonadjacent pairs of vertices . -connectivity is also called "biconnectivity" and  -connectivity is also called "triconnectivity". A graph which is connected but not -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 is a set of edges whose removal renders the graph disconnected. The "edge-connectivity" is the size of a smallest edge cut, and the local edge-connectivity of two vertices is the size of a smallest edge cut disconnecting from . Again, local edge-connectivity is symmetric. A graph is  called "-edge-connected" if its edge connectivity is 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 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 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 of is called a non-trivial cutset if does not contain the neighborhood of any vertex . Then the "superconnectivity" κ1 of G is: Connectivity