{{Short description|Basic concept of graph theory}} [[File:Network Community Structure.svg|thumb|This graph becomes disconnected when the right-most node in the gray area on the left is removed]] [[File:Sample-graph.jpg|thumb|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 [[Connected component (graph theory)|isolated subgraphs]].<ref name="diestel" /> It is closely related to the theory of [[flow network|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|thumb|With vertex 0, this graph is disconnected. The rest of the graph is connected.]] In an [[undirected graph]] {{mvar|G}}, two [[vertex (graph theory)|vertices]] {{mvar|u}} and {{mvar|v}} are called '''connected''' if {{mvar|G}} contains a [[Path (graph theory)|path]] from {{mvar|u}} to {{mvar|v}}. Otherwise, they are called '''disconnected'''. If the two vertices are additionally connected by a path of length {{math|1}} (that is, they are the endpoints of a single edge), the vertices are called '''adjacent'''.

A [[Graph (discrete mathematics)|graph]] is said to be '''connected''' if every pair of vertices in the graph is connected. This means that there is a [[Path (graph theory)|path]] between every pair of vertices. An undirected graph that is not connected is called '''disconnected'''. An undirected graph {{mvar|G}} is therefore disconnected if there exist two vertices in {{mvar|G}} such that no path in {{mvar|G}} has these vertices as endpoints. A graph with just one vertex is connected. An [[Null graph|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 {{mvar|u}} to {{mvar|v}} or a directed path from {{mvar|v}} to {{mvar|u}} for every pair of vertices {{math|''u'', ''v''}}.<ref>[https://users.metu.edu.tr/aldoks/341/tdk%20Chap%2011%20Digraphs.pdf#page=6 Chapter 11: Digraphs: Principle of duality for digraphs: Definition]</ref> It is '''strongly connected''', or simply strong, if it contains a directed path from {{mvar|u}} to {{mvar|v}} and a directed path from {{mvar|v}} to {{mvar|u}} for every pair of vertices {{math|''u'', ''v''}}.

== Components and cuts == A [[connected component (graph theory)|'''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 [[strongly connected component|'''strong components''']] are the maximal strongly connected subgraphs of a directed graph.

A '''[[Cut (graph theory)|vertex cut]]''' or '''separating set''' of a connected graph {{mvar|G}} is a set of vertices whose removal renders {{mvar|G}} disconnected. The [[K-vertex-connected graph|'''vertex connectivity''']] {{math|''κ''(''G'')}} (where {{mvar|G}} is not a [[complete graph]]) is the size of a smallest vertex cut. A graph is called '''''{{mvar|k}}''-vertex-connected''' or '''''{{mvar|k}}''-connected''' if its vertex connectivity is {{mvar|k}} or greater.

More precisely, any graph {{mvar|G}} (complete or not) is said to be ''{{mvar|k}}-vertex-connected'' if it contains at least {{math|''k'' + 1}} vertices, but does not contain a set of {{math|''k'' − 1}} vertices whose removal disconnects the graph; and {{math|''κ''(''G'')}} is defined as the largest {{mvar|k}} such that {{mvar|G}} is {{mvar|k}}-connected. In particular, a [[complete graph]] with {{mvar|n}} vertices, denoted {{mvar|K<sub>n</sub>}}, has no vertex cuts at all, but {{math|''κ''(''K<sub>n</sub>'') {{=}} ''n'' − 1}}.

A '''vertex cut''' for two vertices {{mvar|u}} and {{mvar|v}} is a set of vertices whose removal from the graph disconnects {{mvar|u}} and {{mvar|v}}. The '''local connectivity''' {{math|''κ''(''u'', ''v'')}} is the size of a smallest vertex cut separating {{mvar|u}} and {{mvar|v}}. Local connectivity is symmetric for undirected graphs; that is, {{math|''κ''(''u'', ''v'') {{=}} ''κ''(''v'', ''u'')}}. Moreover, except for complete graphs, {{math|''κ''(''G'')}} equals the minimum of {{math|''κ''(''u'', ''v'')}} over all nonadjacent pairs of vertices {{math|''u'', ''v''}}.

{{math|2}}-connectivity is also called ''[[biconnected graph|biconnectivity]]'' and {{math|3}}-connectivity is also called ''triconnectivity''. A graph {{mvar|G}} which is connected but not {{math|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 (graph theory)|bridge]]''. More generally, an edge cut of {{mvar|G}} is a set of edges whose removal renders the graph disconnected. The ''[[edge-connectivity]]'' {{math|''λ''(''G'')}} is the size of a smallest edge cut, and the local edge-connectivity {{math|''λ''(''u'', ''v'')}} of two vertices {{math|''u'', ''v''}} is the size of a smallest edge cut disconnecting {{mvar|u}} from {{mvar|v}}. Again, local edge-connectivity is symmetric. A graph is called ''{{mvar|k}}-edge-connected'' if its edge connectivity is {{mvar|k}} or greater.

A graph is said to be ''maximally connected'' if its connectivity equals its minimum [[Degree (graph theory)|degree]]. A graph is said to be ''maximally edge-connected'' if its edge-connectivity equals its minimum degree.<ref>{{Cite book | title = Handbook of graph theory | first1 = Jonathan L. | last1 = Gross | first2 = Jay | last2 = Yellen | publisher = [[CRC Press]] | year = 2004 | page = [https://books.google.com/books?id=mKkIGIea_BkC&lpg=PA335&pg=PA335 335] | isbn = 978-1-58488-090-5 | url = https://books.google.com/books?id=mKkIGIea_BkC }}</ref>

=== 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.<ref>{{Cite journal|last1=Liu|first1=Qinghai|last2=Zhang|first2=Zhao|date=2010-03-01|title=The existence and upper bound for two types of restricted connectivity|url=https://www.researchgate.net/publication/235246832|journal=Discrete Applied Mathematics|volume=158|issue=5|pages=516–521|doi=10.1016/j.dam.2009.10.017|doi-access=free}}</ref>

More precisely: a {{mvar|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 {{mvar|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.<ref>{{Cite book | title = Handbook of graph theory | first1 = Jonathan L. | last1 = Gross | first2 = Jay | last2 = Yellen | publisher = [[CRC Press]] | year = 2004 | page = [https://books.google.com/books?id=mKkIGIea_BkC&lpg=PA338&pg=PA338 338] | isbn = 978-1-58488-090-5 | url = https://books.google.com/books?id=mKkIGIea_BkC }}</ref>

A cutset {{mvar|X}} of {{mvar|G}} is called a non-trivial cutset if {{mvar|X}} does not contain the neighborhood {{math|N(''u'')}} of any vertex {{math|''u'' ∉ ''X''}}. Then the ''superconnectivity'' <math>\kappa_1</math> of {{mvar|G}} is <math display="block">\kappa_1(G) = \min\{ |X| : X \text{ is a non-trivial cutset} \}.</math>

A non-trivial edge-cut and the ''edge-superconnectivity'' <math>\lambda_1(G)</math> are defined analogously.<ref>{{Cite journal|last1=Balbuena|first1=Camino|last2=Carmona|first2=Angeles|date=2001-10-01|title=On the connectivity and superconnectivity of bipartite digraphs and graphs|journal=Ars Combinatorica|volume=61|pages=3–22|citeseerx=10.1.1.101.1458}}</ref>

== Menger's theorem == {{Main|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 {{mvar|u}} and {{mvar|v}} are vertices of a graph {{mvar|G}}, then a collection of paths between {{mvar|u}} and {{mvar|v}} is called independent if no two of them share a vertex (other than {{mvar|u}} and {{mvar|v}} themselves). Similarly, the collection is edge-independent if no two paths in it share an edge. The number of mutually independent paths between {{mvar|u}} and {{mvar|v}} is written as {{math|''κ''′(''u'', ''v'')}}, and the number of mutually edge-independent paths between {{mvar|u}} and {{mvar|v}} is written as {{math|''λ''′(''u'', ''v'')}}.

Menger's theorem asserts that for distinct vertices ''u'',''v'', {{math|''λ''(''u'', ''v'')}} equals {{math|''λ''′(''u'', ''v'')}}, and if ''u'' is also not adjacent to ''v'' then {{math|''κ''(''u'', ''v'')}} equals {{math|''κ''′(''u'', ''v'')}}.<ref>{{cite book|title=Algorithmic Graph Theory| author=Gibbons, A.|year=1985|publisher=[[Cambridge University Press]]}}</ref><ref>{{cite book|title=Algorithmic Aspects of Graph Connectivity|author1=Nagamochi, H. |author2=Ibaraki, T.|author2-link=Toshihide Ibaraki | year=2008 |publisher=Cambridge University Press}}</ref> 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#Applications|disjoint-set data structure]]), or to count the number of connected components. A simple algorithm might be written in [[pseudo-code]] as follows:

#Begin at any arbitrary node of the graph {{mvar|G}}. #Proceed from that node using either depth-first or breadth-first search, counting all nodes reached. #Once the graph has been entirely traversed, if the number of nodes counted is equal to the number of nodes of {{mvar|G}}, the graph is connected; otherwise it is disconnected.

By [[Menger's theorem]], for any two vertices {{mvar|u}} and {{mvar|v}} in a connected graph {{mvar|G}}, the numbers {{math|''κ''(''u'', ''v'')}} and {{math|''λ''(''u'', ''v'')}} can be determined efficiently using the [[Max flow min cut|max-flow min-cut]] algorithm. The connectivity and edge-connectivity of {{mvar|G}} can then be computed as the minimum values of {{math|''κ''(''u'', ''v'')}} and {{math|''λ''(''u'', ''v'')}}, respectively.

In [[computational complexity theory]], [[SL (complexity)|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 (complexity)|L]] by [[Omer Reingold]] in 2004.<ref>{{Cite journal|first=Omer|last=Reingold|author-link=Omer Reingold|title=Undirected connectivity in log-space|journal=[[Journal of the ACM]]|year=2008|volume=55|issue=4|pages=1–24| doi=10.1145/1391289.1391291|s2cid=207168478}}</ref> Hence, undirected graph connectivity may be solved in {{math|O(log ''n'')}} space.

The problem of computing the probability that a [[Bernoulli distribution|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 [[sharp-P|#P]]-hard.<ref>{{cite journal | last1 = Provan | first1 = J. Scott | last2 = Ball | first2 = Michael O. | doi = 10.1137/0212053 | issue = 4 | journal = [[SIAM Journal on Computing]] | mr = 721012 | pages = 777–788 | title = The complexity of counting cuts and of computing the probability that a graph is connected | volume = 12 | year = 1983}}.</ref>

=== Number of connected graphs === {{Main|Graph enumeration}} The number of distinct connected labeled graphs with ''n'' nodes is tabulated in the [[On-Line Encyclopedia of Integer Sequences]] as sequence {{OEIS link|A001187}}. The first few non-trivial terms are [[File:The number of connected graphs with 4 vertices.png|thumb|The number and images of connected graphs with 4 nodes]] {| class="wikitable" style="margin:1em auto;" ! ''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 {{math|0}}. * {{math|1}}-connectedness is equivalent to connectedness for graphs of at least two vertices. * The [[complete graph]] on {{mvar|n}} vertices has edge-connectivity equal to {{math|''n'' − 1}}. Every other [[simple graph]] on {{mvar|n}} vertices has strictly smaller edge-connectivity. * In a [[tree (graph theory)|tree]], the local edge-connectivity between any two distinct vertices is {{math|1}}.

== Bounds on connectivity == * The vertex-connectivity of a graph is less than or equal to its edge-connectivity. That is, {{math|''κ''(''G'') ≤ ''λ''(''G'')}}. * The edge-connectivity for a graph with at least 2 vertices is less than or equal to the minimum [[Degree (graph theory)|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.<ref name="diestel">{{cite web|last=Diestel|first=R.|url=http://diestel-graph-theory.com/GrTh.html|title=Graph Theory, Electronic Edition|date=2005|pages=12}}</ref> * For a [[vertex-transitive graph]] of degree {{mvar|d}}, we have: {{math|2(''d'' + 1)/3 ≤ ''κ''(''G'') ≤ ''λ''(''G'') {{=}} ''d''}}.<ref name="GandR">{{cite book|title=Algebraic Graph Theory| last1=Godsil | first1=C. |author1-link=Chris Godsil| last2=Royle| first2=G.| author2-link=Gordon Royle|year=2001|publisher=Springer Verlag}}</ref> * For a vertex-transitive graph of degree {{math|''d'' ≤ 4}}, or for any (undirected) minimal [[Cayley graph]] of degree {{mvar|d}}, or for any [[symmetric graph]] of degree {{mvar|d}}, both kinds of connectivity are equal: {{math|''κ''(''G'') {{=}} ''λ''(''G'') {{=}} ''d''}}.<ref>{{cite book|title=Automorphism groups, isomorphism, reconstruction|series=Technical Report TR-94-10|author=Babai, L.|author-link=László Babai|year=1996|publisher=University of Chicago|url=http://www.cs.uchicago.edu/files/tr_authentic/TR-94-10.ps|url-status=dead|archive-url=https://web.archive.org/web/20100611212234/http://www.cs.uchicago.edu/files/tr_authentic/TR-94-10.ps|archive-date=2010-06-11}} Chapter 27 of ''The Handbook of Combinatorics''.</ref>

== Other properties == * Connectedness is preserved by [[graph homomorphism]]s. * If {{mvar|G}} is connected then its [[line graph]] {{math|''L''(''G'')}} is also connected. * A graph {{mvar|G}} is {{math|2}}-edge-connected if and only if it has an orientation that is strongly connected. * [[Balinski's theorem]] states that the [[polytopal graph]] ({{math|1}}-[[Skeleton (topology)|skeleton]]) of a {{mvar|k}}-dimensional [[convex polytope]] is a {{mvar|k}}-vertex-connected graph.<ref>{{cite journal|author = Balinski, M. L.|title = On the graph structure of convex polyhedra in {{mvar|n}}-space|journal = [[Pacific Journal of Mathematics]]|volume = 11|issue = 2|year = 1961|pages = 431–434|doi = 10.2140/pjm.1961.11.431|doi-access = free}}</ref> [[Ernst Steinitz|Steinitz]]'s previous theorem that any 3-vertex-connected [[planar graph]] is a polytopal graph ([[Steinitz's theorem]]) gives a partial [[converse (logic)|converse]]. * According to a theorem of [[Gabriel Andrew Dirac|G. A. Dirac]], if a graph is {{mvar|k}}-connected for {{math|''k'' ≥ 2}}, then for every set of {{mvar|k}} vertices in the graph there is a [[cycle (graph theory)|cycle]] that passes through all the vertices in the set.<ref>{{Cite journal | last = Dirac | first = Gabriel Andrew | author-link = Gabriel Andrew Dirac | journal = [[Mathematische Nachrichten]] | pages = 61–85 | title = In abstrakten Graphen vorhandene vollständige 4-Graphen und ihre Unterteilungen | volume = 22 | issue = 1–2 | year = 1960 | mr = 0121311 | doi = 10.1002/mana.19600220107}}.</ref><ref>{{Cite journal | last1 = Flandrin | first1 = Evelyne | last2 = Li | first2 = Hao | last3 = Marczyk | first3 = Antoni | last4 = Woźniak | first4 = Mariusz | doi = 10.1016/j.disc.2005.11.052 | issue = 7–8 | journal = Discrete Mathematics | pages = 878–884 | title = A generalization of Dirac's theorem on cycles through {{mvar|k}} vertices in {{mvar|k}}-connected graphs | volume = 307 | year = 2007 | mr = 2297171| doi-access = free }}.</ref> The converse is true when {{math|''k'' {{=}} 2}}.

== See also == * [[Algebraic connectivity]] * [[Cheeger constant (graph theory)]] * [[Dynamic connectivity]], [[Disjoint-set data structure]] * [[Expander graph]] * [[Strength of a graph]]

== References == {{reflist}}

[[Category:Graph connectivity| ]]