Edge connectivity

Edge connectivity --- реберная связность.

We define the edge-connectivity, [math]\displaystyle{ K_{e}(G) }[/math] or [math]\displaystyle{ K_{e} }[/math], for the connected graph [math]\displaystyle{ G }[/math] to be the size of the smallest cut-set of [math]\displaystyle{ G }[/math]. [math]\displaystyle{ G }[/math] is said to be [math]\displaystyle{ h }[/math]-edge-connected for any positive integer [math]\displaystyle{ h }[/math] satisfying [math]\displaystyle{ h \leq K_{e}(G) }[/math]. We denote the smallest degree of any vertex in a graph by [math]\displaystyle{ \delta }[/math]. Since the set of edges incident with any vertex forms a cut-set, we have [math]\displaystyle{ \delta \geq K_{e}(G) }[/math].

For any connected graph [math]\displaystyle{ G }[/math]:

[math]\displaystyle{ K_{v}(G) \leq K_{e}(G) \leq \delta. }[/math]

[math]\displaystyle{ K_{v}(G) }[/math] is the vertex-connectivity.

The local-edge-connectivity [math]\displaystyle{ \lambda(u,v) }[/math] of two vertices [math]\displaystyle{ u }[/math] and [math]\displaystyle{ v }[/math] in a graph or digraph [math]\displaystyle{ D }[/math] is the maximum number of edge-disjoint [math]\displaystyle{ u-v }[/math]-paths in [math]\displaystyle{ D }[/math], and the edge-connectivity of [math]\displaystyle{ D }[/math] is defined as [math]\displaystyle{ \lambda(D) = \min\{\lambda(u,v) | u,v \in V(D)\} }[/math].