k-edge-connected graph

<h2 id="formal-definition">Formal definition</h2>

Let 
 
 
 
 G
 =
 (
 V
 ,
 E
 )
 
 
 {\displaystyle G=(V,E)}
 
 be an arbitrary graph.
If the <a href="/facts/Glossary_of_graph_theory/W0MqKkyE">subgraph</a> 
 
 
 
 
 G
 ′
 
 =
 (
 V
 ,
 E
 ∖
 X
 )
 
 
 {\displaystyle G'=(V,E\setminus X)}
 
 is connected for all 
 
 
 
 X
 ⊆
 E
 
 
 {\displaystyle X\subseteq E}
 
 where 
 
 
 
 
 |
 
 X
 
 |
 
 <
 k
 
 
 {\displaystyle |X|<k}
 
, then G is said to be k-edge-connected.
The edge connectivity of 
 
 
 
 G
 
 
 {\displaystyle G}
 
 is the maximum value k such that G is k-edge-connected. The smallest set X whose removal disconnects G is a <a href="/facts/Minimum_cut/xWTNp1hN">minimum cut</a> in G.
The edge connectivity version of <a href="/facts/Menger%27s_theorem/NlHduKXm">Menger's theorem</a> provides an alternative and equivalent characterization, in terms of edge-disjoint paths in the graph. If and only if every two <a href="/facts/Vertex_(graph_theory)/WhlWmL3o">vertices</a> of G form the endpoints of k paths, no two of which share an edge with each other, then G is k-edge-connected. In one direction this is easy: if a system of paths like this exists, then every set X of fewer than k edges is disjoint from at least one of the paths, and the pair of vertices remains connected to each other even after X is deleted. In the other direction, the existence of a system of paths for each pair of vertices in a graph that cannot be disconnected by the removal of few edges can be proven using the <a href="/facts/Max-flow_min-cut_theorem/qrXp2ut7">max-flow min-cut theorem</a> from the theory of <a href="/facts/Flow_network/k0LCoRwD">network flows</a>.

<h2 id="related-concepts">Related concepts</h2>
Minimum <a href="/facts/Degree_(graph_theory)/LnFFpI8v">vertex degree</a> gives a trivial upper bound on edge-connectivity. That is, if a graph 
 
 
 
 G
 =
 (
 V
 ,
 E
 )
 
 
 {\displaystyle G=(V,E)}
 
 is k-edge-connected then it is necessary that k ≤ δ(G), where δ(G) is the minimum degree of any vertex v ∈ V. Deleting all edges incident to a vertex v would disconnect v from the graph.
Edge connectivity is the dual concept to <a href="/facts/Girth_(graph_theory)/rPwRGgxj">girth</a>, the length of the shortest cycle in a graph, in the sense that the girth of a <a href="/facts/Planar_graph/plREagr9">planar graph</a> is the edge connectivity of its <a href="/facts/Dual_graph/1t14hhEF">dual graph</a>, and vice versa. These concepts are unified in <a href="/facts/Matroid_theory/5bLcGlRF">matroid theory</a> by the <a href="/facts/Matroid_girth/wbzw6pyg">girth of a matroid</a>, the size of the smallest dependent set in the matroid. For a <a href="/facts/Graphic_matroid/UkEwWWhl">graphic matroid</a>, the matroid girth equals the girth of the underlying graph, while for a co-graphic matroid it equals the edge connectivity.<a class="footnote-ref" id="fnref:2" href="#fn:2">2</a>
The 2-edge-connected graphs can also be characterized by the absence of <a href="/facts/Bridge_(graph_theory)/jNtnscpj">bridges</a>, by the existence of an <a href="/facts/Ear_decomposition/k4m5lI09">ear decomposition</a>, or by <a href="/facts/Robbins%27_theorem/QmA6Gzwj">Robbins' theorem</a> according to which these are exactly the graphs that have a <a href="/facts/Strong_orientation/tPzg5DbS">strong orientation</a>.<a class="footnote-ref" id="fnref:3" href="#fn:3">3</a>

<h2 id="computational-aspects">Computational aspects</h2>
There is a polynomial-time algorithm to determine the largest k for which a graph G is k-edge-connected. A simple algorithm would, for every pair (u,v), determine the <a href="/facts/Maximum_flow_problem/aSal0FGF">maximum flow</a> from u to v with the capacity of all edges in G set to 1 for both directions. A graph is k-edge-connected if and only if the maximum flow from u to v is at least k for any pair (u,v), so k is the least u-v-flow among all (u,v).
If n is the number of vertices in the graph, this simple algorithm would perform 
 
 
 
 O
 (
 
 n
 
 2
 
 
 )
 
 
 {\displaystyle O(n^{2})}
 
 iterations of the Maximum flow problem, which can be solved in 
 
 
 
 O
 (
 
 n
 
 3
 
 
 )
 
 
 {\displaystyle O(n^{3})}
 
 time. Hence the complexity of the simple algorithm described above is 
 
 
 
 O
 (
 
 n
 
 5
 
 
 )
 
 
 {\displaystyle O(n^{5})}
 
 in total.
An improved algorithm will solve the maximum flow problem for every pair (u,v) where u is arbitrarily fixed while v varies
over all vertices. This reduces the complexity to 
 
 
 
 O
 (
 
 n
 
 4
 
 
 )
 
 
 {\displaystyle O(n^{4})}
 
 and is sound since, if a <a href="/facts/Cut_(graph_theory)/1lKf2IIW">cut</a> of capacity less than k exists,
it is bound to separate u from some other vertex. It can be further improved by an algorithm of <a href="/facts/Harold_N._Gabow/gLt88dfp">Gabow</a> that runs in worst case 
 
 
 
 O
 (
 
 n
 
 3
 
 
 )
 
 
 {\displaystyle O(n^{3})}
 
 time. <a class="footnote-ref" id="fnref:4" href="#fn:4">4</a>
The Karger–Stein variant of <a href="/facts/Karger%27s_algorithm/D58kwvgc">Karger's algorithm</a> provides a faster <a href="/facts/Randomized_algorithm/Fngl1zgk">randomized algorithm</a> for determining the connectivity, with expected runtime 
 
 
 
 O
 (
 
 n
 
 2
 
 
 
 log
 
 3
 
 
 ⁡
 n
 )
 
 
 {\displaystyle O(n^{2}\log ^{3}n)}
 
.<a class="footnote-ref" id="fnref:5" href="#fn:5">5</a>
A related problem: finding the minimum k-edge-connected spanning subgraph of G (that is: select as few as possible edges in G that your selection is k-edge-connected) is NP-hard for 
 
 
 
 k
 ≥
 2
 
 
 {\displaystyle k\geq 2}
 
.<a class="footnote-ref" id="fnref:6" href="#fn:6">6</a>

<h2 id="see-also">See also</h2>
<ul><li><a href="/facts/K-vertex-connected_graph/EST9uf8W">k-vertex-connected graph</a></li>
<li><a href="/facts/Connectivity_(graph_theory)/FSNjsYhz">Connectivity (graph theory)</a></li>
<li><a href="/facts/Matching_preclusion/d7yrUIpY">Matching preclusion</a></li></ul>

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

<ol>
<li id="fn:1">Jordan, Camille (1869). "Sur les assemblages de lignes". Journal für die reine und angewandte Mathematik (in French). 70 (2): 185–190. <a href="/wiki/Camille_Jordan" target="_blank">/wiki/Camille_Jordan</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></li>
<li id="fn:2">Cho, Jung Jin; Chen, Yong; Ding, Yu (2007), "On the (co)girth of a connected matroid", Discrete Applied Mathematics, 155 (18): 2456–2470, doi:10.1016/j.dam.2007.06.015, MR 2365057. <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></li>
<li id="fn:3">Robbins, H. E. (1939). "A theorem on graphs, with an application to a problem on traffic control". American Mathematical Monthly. 46 (5): 281–283. doi:10.2307/2303897. JSTOR 2303897. <a href="/wiki/Herbert_Robbins" target="_blank">/wiki/Herbert_Robbins</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></li>
<li id="fn:4">Harold N. Gabow. A matroid approach to finding edge connectivity and packing arborescences. J. Comput. Syst. Sci., 50(2):259–273, 1995. <a href="/wiki/Harold_N._Gabow" target="_blank">/wiki/Harold_N._Gabow</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></li>
<li id="fn:5">Karger, David R.; Stein, Clifford (1996). "A new approach to the minimum cut problem" (PDF). Journal of the ACM. 43 (4): 601. doi:10.1145/234533.234534. <a href="/wiki/David_Karger" target="_blank">/wiki/David_Karger</a> <a href="#fnref:5" class="footnote-back-ref">↩</a></li>
<li id="fn:6">M.R. Garey and D.S. Johnson. Computers and Intractability: a Guide to the Theory of NP-Completeness. Freeman, San Francisco, CA, 1979. <a href="#fnref:6" class="footnote-back-ref">↩</a></li>
</ol>

k-edge-connected graph open-in-new

k-edge-connected graph