# Connectivity (graph theory)

> Mediated Wiki article. Canonical URL: https://mediated.wiki/source/Connectivity_(graph_theory)
> Markdown URL: https://mediated.wiki/source/Connectivity_(graph_theory).md
> Source: https://en.wikipedia.org/wiki/Connectivity_(graph_theory)
> Source revision: 1282364336
> License: Creative Commons Attribution-ShareAlike 4.0 International (https://creativecommons.org/licenses/by-sa/4.0/)

Basic concept of graph theory

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

This graph becomes disconnected when the dashed edge is removed.

In [mathematics](/source/Mathematics) and [computer science](/source/Computer_science), **connectivity** is one of the basic concepts of [graph theory](/source/Graph_theory): it asks for the [minimum](/source/Minimum) number of elements (nodes or edges) that need to be removed to separate the remaining nodes into two or more [isolated subgraphs](/source/Connected_component_(graph_theory)).[1] It is closely related to the theory of [network flow](/source/Flow_network) 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](/source/Undirected_graph) G, two [vertices](/source/Vertex_(graph_theory)) u and v are called **connected** if G contains a [path](/source/Path_(graph_theory)) 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](/source/Graph_(discrete_mathematics)) is said to be **connected** if every pair of vertices in the graph is connected. This means that there is a [path](/source/Path_(graph_theory)) 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](/source/Null_graph) with two or more vertices is disconnected.

A [directed graph](/source/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**](/source/Connected_component_(graph_theory)) 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](/source/If_and_only_if) it has exactly one connected component.

The [**strong components**](/source/Strongly_connected_component) are the maximal strongly connected subgraphs of a directed graph.

A **[vertex cut](/source/Cut_(graph_theory))** or **separating set** of a connected graph G is a set of vertices whose removal renders G disconnected. The [**vertex connectivity**](/source/K-vertex-connected_graph) *κ*(*G*) (where G is not a [complete graph](/source/Complete_graph)) is the size of a smallest 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](/source/Complete_graph) with n vertices, denoted Kn, has no vertex cuts at all, but *κ*(*Kn*) = *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](/source/Biconnected_graph)* 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](/source/Bridge_(graph_theory))*. More generally, an edge cut of G is a set of edges whose removal renders the graph disconnected. The *[edge-connectivity](/source/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](/source/Degree_(graph_theory)). 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* ∉ *X*. Then the *superconnectivity* κ 1 {\displaystyle \kappa _{1}} of G is κ 1 ( G ) = min { | X | : X is a non-trivial cutset } . {\displaystyle \kappa _{1}(G)=\min\{|X|:X{\text{ is a non-trivial cutset}}\}.}

A non-trivial edge-cut and the *edge-superconnectivity* λ 1 ( G ) {\displaystyle \lambda _{1}(G)} are defined analogously.[6]

## Menger's theorem

Main article: [Menger's theorem](/source/Menger's_theorem)

One of the most important facts about connectivity in graphs is [Menger's theorem](/source/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](/source/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](/source/Search_algorithm), such as [breadth-first search](/source/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](/source/Disjoint-set_data_structure#Applications)), or to count the number of connected components. A simple algorithm might be written in [pseudo-code](/source/Pseudo-code) as follows:

1. Begin at any arbitrary node of the graph G.

1. Proceed from that node using either depth-first or breadth-first search, counting all nodes reached.

1. 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](/source/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](/source/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](/source/Computational_complexity_theory), [SL](/source/SL_(complexity)) is the class of problems [log-space reducible](/source/Log-space_reducible) to the problem of determining whether two vertices in a graph are connected, which was proved to be equal to [L](/source/L_(complexity)) by [Omer Reingold](/source/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](/source/Bernoulli_distribution) 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](/source/Sharp-P)-hard.[10]

### Number of connected graphs

Main article: [Graph enumeration](/source/Graph_enumeration)

The number of distinct connected labeled graphs with *n* nodes is tabulated in the [On-Line Encyclopedia of Integer Sequences](/source/On-Line_Encyclopedia_of_Integer_Sequences) as sequence [A001187](https://oeis.org/A001187). The first few non-trivial terms are

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](/source/Complete_graph) on n vertices has edge-connectivity equal to *n* − 1. Every other [simple graph](/source/Simple_graph) on n vertices has strictly smaller edge-connectivity.

- In a [tree](/source/Tree_(graph_theory)), 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](/source/Degree_(graph_theory)) 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](/source/Vertex-transitive_graph) of degree d, we have: 2(*d* + 1)/3 ≤ *κ*(*G*) ≤ *λ*(*G*) = *d*.[11]

- For a vertex-transitive graph of degree *d* ≤ 4, or for any (undirected) minimal [Cayley graph](/source/Cayley_graph) of degree d, or for any [symmetric graph](/source/Symmetric_graph) of degree d, both kinds of connectivity are equal: *κ*(*G*) = *λ*(*G*) = *d*.[12]

## Other properties

- Connectedness is preserved by [graph homomorphisms](/source/Graph_homomorphism).

- If G is connected then its [line graph](/source/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](/source/Balinski's_theorem) states that the [polytopal graph](/source/Polytopal_graph) (1-[skeleton](/source/Skeleton_(topology))) of a k-dimensional [convex polytope](/source/Convex_polytope) is a k-vertex-connected graph.[13] [Steinitz](/source/Ernst_Steinitz)'s previous theorem that any 3-vertex-connected [planar graph](/source/Planar_graph) is a polytopal graph ([Steinitz's theorem](/source/Steinitz's_theorem)) gives a partial [converse](/source/Converse_(logic)).

- According to a theorem of [G. A. Dirac](/source/Gabriel_Andrew_Dirac), if a graph is k-connected for *k* ≥ 2, then for every set of k vertices in the graph there is a [cycle](/source/Cycle_(graph_theory)) that passes through all the vertices in the set.[14][15] The converse is true when *k* = 2.

## See also

- [Algebraic connectivity](/source/Algebraic_connectivity)

- [Cheeger constant (graph theory)](/source/Cheeger_constant_(graph_theory))

- [Dynamic connectivity](/source/Dynamic_connectivity), [Disjoint-set data structure](/source/Disjoint-set_data_structure)

- [Expander graph](/source/Expander_graph)

- [Strength of a graph](/source/Strength_of_a_graph)

## References

1. ^ [***a***](#cite_ref-diestel_1-0) [***b***](#cite_ref-diestel_1-1) Diestel, R. (2005). ["Graph Theory, Electronic Edition"](http://diestel-graph-theory.com/GrTh.html). p. 12.

1. **[^](#cite_ref-2)** [Chapter 11: Digraphs: Principle of duality for digraphs: Definition](https://users.metu.edu.tr/aldoks/341/tdk%20Chap%2011%20Digraphs.pdf#page=6)

1. **[^](#cite_ref-3)** Gross, Jonathan L.; Yellen, Jay (2004). [*Handbook of graph theory*](https://books.google.com/books?id=mKkIGIea_BkC). [CRC Press](/source/CRC_Press). p. [335](https://books.google.com/books?id=mKkIGIea_BkC&lpg=PA335&pg=PA335). [ISBN](/source/ISBN_(identifier)) [978-1-58488-090-5](https://en.wikipedia.org/wiki/Special:BookSources/978-1-58488-090-5).

1. **[^](#cite_ref-4)** Liu, Qinghai; Zhang, Zhao (2010-03-01). ["The existence and upper bound for two types of restricted connectivity"](https://www.researchgate.net/publication/235246832). *Discrete Applied Mathematics*. **158** (5): 516–521. [doi](/source/Doi_(identifier)):[10.1016/j.dam.2009.10.017](https://doi.org/10.1016%2Fj.dam.2009.10.017).

1. **[^](#cite_ref-5)** Gross, Jonathan L.; Yellen, Jay (2004). [*Handbook of graph theory*](https://books.google.com/books?id=mKkIGIea_BkC). [CRC Press](/source/CRC_Press). p. [338](https://books.google.com/books?id=mKkIGIea_BkC&lpg=PA338&pg=PA338). [ISBN](/source/ISBN_(identifier)) [978-1-58488-090-5](https://en.wikipedia.org/wiki/Special:BookSources/978-1-58488-090-5).

1. **[^](#cite_ref-6)** Balbuena, Camino; Carmona, Angeles (2001-10-01). "On the connectivity and superconnectivity of bipartite digraphs and graphs". *Ars Combinatorica*. **61**: 3–22. [CiteSeerX](/source/CiteSeerX_(identifier)) [10.1.1.101.1458](https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.101.1458).

1. **[^](#cite_ref-7)** Gibbons, A. (1985). *Algorithmic Graph Theory*. [Cambridge University Press](/source/Cambridge_University_Press).

1. **[^](#cite_ref-8)** Nagamochi, H.; [Ibaraki, T.](/source/Toshihide_Ibaraki) (2008). *Algorithmic Aspects of Graph Connectivity*. Cambridge University Press.

1. **[^](#cite_ref-9)** [Reingold, Omer](/source/Omer_Reingold) (2008). "Undirected connectivity in log-space". *[Journal of the ACM](/source/Journal_of_the_ACM)*. **55** (4): 1–24. [doi](/source/Doi_(identifier)):[10.1145/1391289.1391291](https://doi.org/10.1145%2F1391289.1391291). [S2CID](/source/S2CID_(identifier)) [207168478](https://api.semanticscholar.org/CorpusID:207168478).

1. **[^](#cite_ref-10)** Provan, J. Scott; Ball, Michael O. (1983). "The complexity of counting cuts and of computing the probability that a graph is connected". *[SIAM Journal on Computing](/source/SIAM_Journal_on_Computing)*. **12** (4): 777–788. [doi](/source/Doi_(identifier)):[10.1137/0212053](https://doi.org/10.1137%2F0212053). [MR](/source/MR_(identifier)) [0721012](https://mathscinet.ams.org/mathscinet-getitem?mr=0721012)..

1. **[^](#cite_ref-GandR_11-0)** [Godsil, C.](/source/Chris_Godsil); [Royle, G.](/source/Gordon_Royle) (2001). *Algebraic Graph Theory*. Springer Verlag.

1. **[^](#cite_ref-12)** [Babai, L.](/source/L%C3%A1szl%C3%B3_Babai) (1996). [*Automorphism groups, isomorphism, reconstruction*](https://web.archive.org/web/20100611212234/http://www.cs.uchicago.edu/files/tr_authentic/TR-94-10.ps). Technical Report TR-94-10. University of Chicago. Archived from [the original](http://www.cs.uchicago.edu/files/tr_authentic/TR-94-10.ps) on 2010-06-11. Chapter 27 of *The Handbook of Combinatorics*.

1. **[^](#cite_ref-13)** Balinski, M. L. (1961). ["On the graph structure of convex polyhedra in n-space"](https://doi.org/10.2140%2Fpjm.1961.11.431). *[Pacific Journal of Mathematics](/source/Pacific_Journal_of_Mathematics)*. **11** (2): 431–434. [doi](/source/Doi_(identifier)):[10.2140/pjm.1961.11.431](https://doi.org/10.2140%2Fpjm.1961.11.431).

1. **[^](#cite_ref-14)** [Dirac, Gabriel Andrew](/source/Gabriel_Andrew_Dirac) (1960). "In abstrakten Graphen vorhandene vollständige 4-Graphen und ihre Unterteilungen". *[Mathematische Nachrichten](/source/Mathematische_Nachrichten)*. **22** (1–2): 61–85. [doi](/source/Doi_(identifier)):[10.1002/mana.19600220107](https://doi.org/10.1002%2Fmana.19600220107). [MR](/source/MR_(identifier)) [0121311](https://mathscinet.ams.org/mathscinet-getitem?mr=0121311)..

1. **[^](#cite_ref-15)** Flandrin, Evelyne; Li, Hao; Marczyk, Antoni; Woźniak, Mariusz (2007). ["A generalization of Dirac's theorem on cycles through k vertices in k-connected graphs"](https://doi.org/10.1016%2Fj.disc.2005.11.052). *Discrete Mathematics*. **307** (7–8): 878–884. [doi](/source/Doi_(identifier)):[10.1016/j.disc.2005.11.052](https://doi.org/10.1016%2Fj.disc.2005.11.052). [MR](/source/MR_(identifier)) [2297171](https://mathscinet.ams.org/mathscinet-getitem?mr=2297171)..

---
Adapted from the Wikipedia article [Connectivity (graph theory)](https://en.wikipedia.org/wiki/Connectivity_(graph_theory)) by Wikipedia contributors ([contributor history](https://en.wikipedia.org/wiki/Connectivity_(graph_theory)?action=history)). Available under [Creative Commons Attribution-ShareAlike 4.0 International](https://creativecommons.org/licenses/by-sa/4.0/). Changes may have been made.