Connectivity (graph theory)

<h2 id="connected-vertices-and-graphs">Connected vertices and graphs</h2>

In an <a href="/facts/Undirected_graph/kw3eIBUe">undirected graph</a> G, two <a href="/facts/Vertex_(graph_theory)/WhlWmL3o">vertices</a> u and v are called connected if G contains a <a href="/facts/Path_(graph_theory)/WMsq21Nf">path</a> 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 <a href="/facts/Graph_(discrete_mathematics)/kw3eIBUe">graph</a> is said to be connected if every pair of vertices in the graph is connected. This means that there is a <a href="/facts/Path_(graph_theory)/WMsq21Nf">path</a> 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 <a href="/facts/Null_graph/Ro1YV0g6">edgeless graph</a> with two or more vertices is disconnected.
A <a href="/facts/Directed_graph/YBdfQ0um">directed graph</a> 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.<a class="footnote-ref" id="fnref:2" href="#fn:2">2</a> 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.

<h2 id="components-and-cuts">Components and cuts</h2>
A <a href="/facts/Connected_component_(graph_theory)/5owVSXtY">connected component</a> 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 <a href="/facts/If_and_only_if/bYSxGJ66">if and only if</a> it has exactly one connected component.
The <a href="/facts/Strongly_connected_component/P6rBqb7W">strong components</a> are the maximal strongly connected subgraphs of a directed graph.
A <a href="/facts/Cut_(graph_theory)/1lKf2IIW">vertex cut</a> or separating set of a connected graph G is a set of vertices whose removal renders G disconnected. The <a href="/facts/K-vertex-connected_graph/EST9uf8W">vertex connectivity</a> κ(G) (where G is not a <a href="/facts/Complete_graph/AYD6hUqI">complete graph</a>) 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 <a href="/facts/Complete_graph/AYD6hUqI">complete graph</a> 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 <a href="/facts/Biconnected_graph/sTfSnFkM">biconnectivity</a> 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 <a href="/facts/Bridge_(graph_theory)/jNtnscpj">bridge</a>. More generally, an edge cut of G is a set of edges whose removal renders the graph disconnected. The <a href="/facts/Edge-connectivity/vJN0po8s">edge-connectivity</a> λ(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 <a href="/facts/Degree_(graph_theory)/LnFFpI8v">degree</a>. A graph is said to be maximally edge-connected if its edge-connectivity equals its minimum degree.<a class="footnote-ref" id="fnref:3" href="#fn:3">3</a>

<h3>Super- and hyper-connectivity</h3>
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.<a class="footnote-ref" id="fnref:4" href="#fn:4">4</a>
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.<a class="footnote-ref" id="fnref:5" href="#fn:5">5</a>
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.<a class="footnote-ref" id="fnref:6" href="#fn:6">6</a>

<h2 id="mengers-theorem">Menger's theorem</h2>
Main article: <a href="/facts/Menger%27s_theorem/NlHduKXm">Menger's theorem</a>
One of the most important facts about connectivity in graphs is <a href="/facts/Menger%27s_theorem/NlHduKXm">Menger's theorem</a>, 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).<a class="footnote-ref" id="fnref:7" href="#fn:7">7</a><a class="footnote-ref" id="fnref:8" href="#fn:8">8</a> This fact is actually a special case of the <a href="/facts/Max-flow_min-cut_theorem/qrXp2ut7">max-flow min-cut theorem</a>.

<h2 id="computational-aspects">Computational aspects</h2>
The problem of determining whether two vertices in a graph are connected can be solved efficiently using a <a href="/facts/Search_algorithm/eJuw0nyz">search algorithm</a>, such as <a href="/facts/Breadth-first_search/2kulDXCx">breadth-first search</a>. More generally, it is easy to determine computationally whether a graph is connected (for example, by using a <a href="/facts/Disjoint-set_data_structure/QnFQNedE">disjoint-set data structure</a>), or to count the number of connected components. A simple algorithm might be written in <a href="/facts/Pseudo-code/XgN19duK">pseudo-code</a> as follows:

<ol><li>Begin at any arbitrary node of the graph G.</li>
<li>Proceed from that node using either depth-first or breadth-first search, counting all nodes reached.</li>
<li>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.</li></ol>
By <a href="/facts/Menger%27s_theorem/NlHduKXm">Menger's theorem</a>, 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 <a href="/facts/Max_flow_min_cut/qrXp2ut7">max-flow min-cut</a> algorithm. The connectivity and edge-connectivity of G can then be computed as the minimum values of κ(u, v) and λ(u, v), respectively.
In <a href="/facts/Computational_complexity_theory/etHuVF3U">computational complexity theory</a>, <a href="/facts/SL_(complexity)/NHcut8wL">SL</a> is the class of problems <a href="/facts/Log-space_reducible/eDwttWhn">log-space reducible</a> to the problem of determining whether two vertices in a graph are connected, which was proved to be equal to <a href="/facts/L_(complexity)/vCMV0edS">L</a> by <a href="/facts/Omer_Reingold/MaaTa9CF">Omer Reingold</a> in 2004.<a class="footnote-ref" id="fnref:9" href="#fn:9">9</a> Hence, undirected graph connectivity may be solved in O(log n) space.
The problem of computing the probability that a <a href="/facts/Bernoulli_distribution/ChCtYyvs">Bernoulli</a> 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 <a href="/facts/Sharp-P/tY95TU7t">#P</a>-hard.<a class="footnote-ref" id="fnref:10" href="#fn:10">10</a>

<h3>Number of connected graphs</h3>
Main article: <a href="/facts/Graph_enumeration/3AgPDEAV">Graph enumeration</a>
The number of distinct connected labeled graphs with n nodes is tabulated in the <a href="/facts/On-Line_Encyclopedia_of_Integer_Sequences/yow6cVsU">On-Line Encyclopedia of Integer Sequences</a> as sequence A001187. The first few non-trivial terms are

<table><tbody><tr><th>n</th><th>graphs</th></tr><tr><th>1</th><td>1</td></tr><tr><th>2</th><td>1</td></tr><tr><th>3</th><td>4</td></tr><tr><th>4</th><td>38</td></tr><tr><th>5</th><td>728</td></tr><tr><th>6</th><td>26704</td></tr><tr><th>7</th><td>1866256</td></tr><tr><th>8</th><td>251548592</td></tr></tbody></table>
<h2 id="examples">Examples</h2>
<ul><li>The vertex- and edge-connectivities of a disconnected graph are both 0.</li>
<li>1-connectedness is equivalent to connectedness for graphs of at least two vertices.</li>
<li>The <a href="/facts/Complete_graph/AYD6hUqI">complete graph</a> on n vertices has edge-connectivity equal to n − 1. Every other <a href="/facts/Simple_graph/kw3eIBUe">simple graph</a> on n vertices has strictly smaller edge-connectivity.</li>
<li>In a <a href="/facts/Tree_(graph_theory)/TCWk4Joy">tree</a>, the local edge-connectivity between any two distinct vertices is 1.</li></ul>
<h2 id="bounds-on-connectivity">Bounds on connectivity</h2>
<ul><li>The vertex-connectivity of a graph is less than or equal to its edge-connectivity. That is, κ(G) ≤ λ(G).</li>
<li>The edge-connectivity for a graph with at least 2 vertices is less than or equal to the minimum <a href="/facts/Degree_(graph_theory)/LnFFpI8v">degree</a> 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.<a class="footnote-ref" id="fnref:11" href="#fn:11">11</a></li>
<li>For a <a href="/facts/Vertex-transitive_graph/042b7rD7">vertex-transitive graph</a> of degree d, we have: 2(d + 1)/3 ≤ κ(G) ≤ λ(G) = d.<a class="footnote-ref" id="fnref:12" href="#fn:12">12</a></li>
<li>For a vertex-transitive graph of degree d ≤ 4, or for any (undirected) minimal <a href="/facts/Cayley_graph/QxoxNnys">Cayley graph</a> of degree d, or for any <a href="/facts/Symmetric_graph/vPVWrnjb">symmetric graph</a> of degree d, both kinds of connectivity are equal: κ(G) = λ(G) = d.<a class="footnote-ref" id="fnref:13" href="#fn:13">13</a></li></ul>
<h2 id="other-properties">Other properties</h2>
<ul><li>Connectedness is preserved by <a href="/facts/Graph_homomorphism/XSljQ25z">graph homomorphisms</a>.</li>
<li>If G is connected then its <a href="/facts/Line_graph/RWNxSy5j">line graph</a> L(G) is also connected.</li>
<li>A graph G is 2-edge-connected if and only if it has an orientation that is strongly connected.</li>
<li><a href="/facts/Balinski%27s_theorem/MCqlLEcz">Balinski's theorem</a> states that the <a href="/facts/Polytopal_graph/2pRHcRgC">polytopal graph</a> (1-<a href="/facts/Skeleton_(topology)/EAt2F7tC">skeleton</a>) of a k-dimensional <a href="/facts/Convex_polytope/2pRHcRgC">convex polytope</a> is a k-vertex-connected graph.<a class="footnote-ref" id="fnref:14" href="#fn:14">14</a> <a href="/facts/Ernst_Steinitz/jX6HsXLf">Steinitz</a>'s previous theorem that any 3-vertex-connected <a href="/facts/Planar_graph/plREagr9">planar graph</a> is a polytopal graph (<a href="/facts/Steinitz%27s_theorem/FEq947FE">Steinitz's theorem</a>) gives a partial <a href="/facts/Converse_(logic)/VhlUrxxx">converse</a>.</li>
<li>According to a theorem of <a href="/facts/Gabriel_Andrew_Dirac/A5jNDFc3">G. A. Dirac</a>, if a graph is k-connected for k ≥ 2, then for every set of k vertices in the graph there is a <a href="/facts/Cycle_(graph_theory)/Is44edrv">cycle</a> that passes through all the vertices in the set.<a class="footnote-ref" id="fnref:15" href="#fn:15">15</a><a class="footnote-ref" id="fnref:16" href="#fn:16">16</a> The converse is true when k = 2.</li></ul>
<h2 id="see-also">See also</h2>
<ul><li><a href="/facts/Algebraic_connectivity/z7kP4K3s">Algebraic connectivity</a></li>
<li><a href="/facts/Cheeger_constant_(graph_theory)/hPDzmgW6">Cheeger constant (graph theory)</a></li>
<li><a href="/facts/Dynamic_connectivity/L0DX80bl">Dynamic connectivity</a>, <a href="/facts/Disjoint-set_data_structure/QnFQNedE">Disjoint-set data structure</a></li>
<li><a href="/facts/Expander_graph/21stncb0">Expander graph</a></li>
<li><a href="/facts/Strength_of_a_graph/zDSpAjRb">Strength of a graph</a></li></ul>

<h2 id="references">References</h2>

<ol>
<li id="fn:1">Diestel, R. (2005). "Graph Theory, Electronic Edition". p. 12. <a href="http://diestel-graph-theory.com/GrTh.html" target="_blank">http://diestel-graph-theory.com/GrTh.html</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></li>
<li id="fn:2">Chapter 11: Digraphs: Principle of duality for digraphs: Definition <a href="https://users.metu.edu.tr/aldoks/341/tdk%20Chap%2011%20Digraphs.pdf#page=6" target="_blank">https://users.metu.edu.tr/aldoks/341/tdk%20Chap%2011%20Digraphs.pdf#page=6</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></li>
<li id="fn:3">Gross, Jonathan L.; Yellen, Jay (2004). Handbook of graph theory. CRC Press. p. 335. ISBN 978-1-58488-090-5. <a href="978-1-58488-090-5" target="_blank">978-1-58488-090-5</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></li>
<li id="fn:4">Liu, Qinghai; Zhang, Zhao (2010-03-01). "The existence and upper bound for two types of restricted connectivity". Discrete Applied Mathematics. 158 (5): 516–521. doi:10.1016/j.dam.2009.10.017. <a href="https://www.researchgate.net/publication/235246832" target="_blank">https://www.researchgate.net/publication/235246832</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></li>
<li id="fn:5">Gross, Jonathan L.; Yellen, Jay (2004). Handbook of graph theory. CRC Press. p. 338. ISBN 978-1-58488-090-5. <a href="978-1-58488-090-5" target="_blank">978-1-58488-090-5</a> <a href="#fnref:5" class="footnote-back-ref">↩</a></li>
<li id="fn:6">Balbuena, Camino; Carmona, Angeles (2001-10-01). "On the connectivity and superconnectivity of bipartite digraphs and graphs". Ars Combinatorica. 61: 3–22. CiteSeerX 10.1.1.101.1458. <a href="/wiki/CiteSeerX_(identifier)" target="_blank">/wiki/CiteSeerX_(identifier)</a> <a href="#fnref:6" class="footnote-back-ref">↩</a></li>
<li id="fn:7">Gibbons, A. (1985). Algorithmic Graph Theory. Cambridge University Press. <a href="/wiki/Cambridge_University_Press" target="_blank">/wiki/Cambridge_University_Press</a> <a href="#fnref:7" class="footnote-back-ref">↩</a></li>
<li id="fn:8">Nagamochi, H.; Ibaraki, T. (2008). Algorithmic Aspects of Graph Connectivity. Cambridge University Press. <a href="/wiki/Toshihide_Ibaraki" target="_blank">/wiki/Toshihide_Ibaraki</a> <a href="#fnref:8" class="footnote-back-ref">↩</a></li>
<li id="fn:9">Reingold, Omer (2008). "Undirected connectivity in log-space". Journal of the ACM. 55 (4): 1–24. doi:10.1145/1391289.1391291. S2CID 207168478. <a href="/wiki/Omer_Reingold" target="_blank">/wiki/Omer_Reingold</a> <a href="#fnref:9" class="footnote-back-ref">↩</a></li>
<li id="fn: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. 12 (4): 777–788. doi:10.1137/0212053. MR 0721012.. <a href="/wiki/SIAM_Journal_on_Computing" target="_blank">/wiki/SIAM_Journal_on_Computing</a> <a href="#fnref:10" class="footnote-back-ref">↩</a></li>
<li id="fn:11">Diestel, R. (2005). "Graph Theory, Electronic Edition". p. 12. <a href="http://diestel-graph-theory.com/GrTh.html" target="_blank">http://diestel-graph-theory.com/GrTh.html</a> <a href="#fnref:11" class="footnote-back-ref">↩</a></li>
<li id="fn:12">Godsil, C.; Royle, G. (2001). Algebraic Graph Theory. Springer Verlag. <a href="/wiki/Chris_Godsil" target="_blank">/wiki/Chris_Godsil</a> <a href="#fnref:12" class="footnote-back-ref">↩</a></li>
<li id="fn:13">Babai, L. (1996). Automorphism groups, isomorphism, reconstruction. Technical Report TR-94-10. University of Chicago. Archived from the original on 2010-06-11. Chapter 27 of The Handbook of Combinatorics. <a href="/wiki/L%C3%A1szl%C3%B3_Babai" target="_blank">/wiki/L%C3%A1szl%C3%B3_Babai</a> <a href="#fnref:13" class="footnote-back-ref">↩</a></li>
<li id="fn:14">Balinski, M. L. (1961). "On the graph structure of convex polyhedra in n-space". Pacific Journal of Mathematics. 11 (2): 431–434. doi:10.2140/pjm.1961.11.431. <a href="https://doi.org/10.2140%2Fpjm.1961.11.431" target="_blank">https://doi.org/10.2140%2Fpjm.1961.11.431</a> <a href="#fnref:14" class="footnote-back-ref">↩</a></li>
<li id="fn:15">Dirac, Gabriel Andrew (1960). "In abstrakten Graphen vorhandene vollständige 4-Graphen und ihre Unterteilungen". Mathematische Nachrichten. 22 (1–2): 61–85. doi:10.1002/mana.19600220107. MR 0121311.. <a href="/wiki/Gabriel_Andrew_Dirac" target="_blank">/wiki/Gabriel_Andrew_Dirac</a> <a href="#fnref:15" class="footnote-back-ref">↩</a></li>
<li id="fn:16">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". Discrete Mathematics. 307 (7–8): 878–884. doi:10.1016/j.disc.2005.11.052. MR 2297171.. <a href="https://doi.org/10.1016%2Fj.disc.2005.11.052" target="_blank">https://doi.org/10.1016%2Fj.disc.2005.11.052</a> <a href="#fnref:16" class="footnote-back-ref">↩</a></li>
</ol>

Connectivity (graph theory) open-in-new

Connectivity (graph theory)