View source for Graph, connectivity of a

<!--
g0449101.png
$#A+1 = 97 n = 0
$#C+1 = 97 : ~/encyclopedia/old_files/data/G044/G.0404910 Graph, connectivity of a
Automatically converted into TeX, above some diagnostics.
Please remove this comment and the {{TEX|auto}} line below,
if TeX found to be correct.
-->

{{TEX|auto}}
{{TEX|done}}

One of the topological characteristics of a graph. A graph is said to be connected if for any two of its vertices  $  u $
and  $  v $
there exists a chain connecting these vertices. The vertex connectivity number of a graph  $  G $(
denoted by  $  \kappa ( G) $) 
is the smallest number of vertices the removal of which results in a disconnected graph or in a graph consisting of one isolated vertex. The edge connectivity number (denoted by  $  \lambda ( G) $) 
is the smallest number of edges of  $  G $
the removal of which results in a disconnected graph. A graph  $  G $
is said to be  $  k $-
connected if  $  \kappa ( G) \geq  k $, 
and  $  k $-
edge-connected if  $  \lambda ( G) \geq  k $. 
A maximal  $  k $-
connected subgraph of a graph  $  G $
is said to be a  $  k $-
connected component of it; a  $  1 $-
connected component is called a connected component. In studying communication networks and logical networks, the connectivity numbers of the corresponding graphs can be interpreted as a degree of reliability of these networks.

The theory of graphs studies methods for determining the connectivity of graphs, conditions under which a graph is  $  k $-
connected or  $  k $-
edge-connected, the relations between the different types of connectivity, the dependence of the connectivity numbers on other graph parameters, etc. Thus, if  $  \delta ( G) $
is the minimal degree of the vertices of a graph  $  G $, 
the following inequalities are valid:  $  \kappa ( G) \leq  \lambda ( G) \leq  \delta ( G) $.

For any integers  $  a, b, c $(
$  0 < a \leq  b \leq  c $) 
there exists a graph  $  G $
for which  $  \kappa ( G) = a $, 
$  \lambda ( G) = b $, 
$  \delta ( G) = c $. 
If  $  G $
has  $  n $
vertices and  $  \delta ( G) \geq  [ n/2] $, 
then  $  \lambda ( G) = \delta ( G) $. 
One says that a set  $  S $
of vertices, edges, or vertices and edges separates two vertices  $  u $
and  $  v $
if  $  u $
and  $  v $
belong to different connected components of the graph  $  G- S $
obtained from  $  G $
by the removal of the elements of  $  S $. 
The following statements are valid.

The smallest number of vertices separating two non-adjacent vertices  $  u $
and  $  v $
is equal to the largest number of simple chains without common vertices connecting  $  u $
and  $  v $. 
A graph  $  G $
is  $  k $-
connected if and only if any pair of its vertices is connected by at least  $  k $
chains which do not intersect at the vertices. Similar theorems are also valid for edge connectivity. A graph is  $  k $-
edge-connected if and only if any pair of its vertices is connected by at least  $  k $
chains which do not intersect at the edges. A set of edges whose removal results in the formation of a disconnected graph is known as a cut. In each graph the largest number of cuts which do not intersect at the edges and which separate two vertices  $  u $
and  $  v $
is equal to the smallest number of edges of a simple chain connecting  $  u $
and  $  v $, 
i.e. to the distance  $  d ( u , v) $
between  $  u $
and  $  v $.

====References====
<table><TR><TD valign="top">[1]</TD> <TD valign="top">  F. Harary,   "Graph theory" , Addison-Wesley  (1969)  pp. Chapt. 9</TD></TR><TR><TD valign="top">[2]</TD> <TD valign="top">  L.R. Ford,   D.R. Fulkerson,   "Flows in networks" , Princeton Univ. Press  (1962)</TD></TR></table>

====Comments====
The assertions in the last section can be derived from the maximum-flow-minimum-cut theorem of L. Ford and D. Fulkerson (see [[#References|[2]]]). The first two are different versions of the vertex form of Menger's theorem (see [[#References|[1]]]).

The maximum-flow-minimum-cut theorem, or the Ford–Fulkerson theorem, deals with a directed graph  $  G $
for which for each arc  $  e $
a capacity  $  0 \leq  c _ {e} < \infty $
is specified. In addition, two special vertices, labeled  $  Q, S $, 
are specified, called source and sink respectively, and there are no arcs leaving  $  S $
or entering  $  Q $. 
A flow on the graph is given by specifying for every arc (i.e. directed edge) a number  $  0 \leq  f _ {e} \leq  c _ {e} $
such that for every vertex  $  P \neq Q, S $,

$$ \tag{* }
\sum _ {a ( e) = P } f _ {e}  = \ 
\sum _ {b ( e) = P } f _ {e}  $$

where for an arc  $  e $, 
$  a ( e) $
denotes its source vertex and  $  b ( e) $
its target vertex. The maximum flow problem asks for a flow such that

$$ 
\sum _ {a ( e) = Q } f _ {e}  $$

is maximized. In this setting a cut is a set of arcs whose removal results in a disconnected graph with  $  Q $
in one component and  $  S $
in another. The capacity of a cut is the sum of the capacities  $  c _ {e} $
of the elements of the cut. The maximum-flow-minimum-cut theorem now says that the maximum flow attainable is equal to the minimal attainable capacity of a cut. The maximum flow problem can be formulated as a linear programming problem, and then the maximum-flow-minimum-cut theorem is an instance of the duality theorem of linear programming.

Recall that a chain in a non-oriented graph from  $  v _ {0} $
to  $  v _ {n} $
is a sequence  $  v _ {0} e _ {0} v _ {1} \dots e _ {n - 1 }  v _ {n} $
of alternating vertices and edges such that  $  e _ {i} $
is an edge between  $  v _ {i} $
and  $  v _ {i + 1 }  $
and such that all  $  e _ {j} $
and all  $  v _ {k} $, 
except possibly  $  v _ {0} $
and  $  v _ {n} $, 
are distinct. A  $  vw $-
disconnecting set or cut, where  $  v, w $
are two vertices, is a set of edges whose removal results in a disconnected graph with  $  v $
in one component and  $  w $
in another. The edge form of Menger's theorem now says that for a connected graph the maximum number of edge-disjoint chains from  $  v $
to  $  w $
is equal to the minimum number of edges in a  $  vw $-
disconnecting set. The theorem was in fact first proved by Ford and Fulkerson (1955). A  $  vw $-
separating set is a set of vertices  $  S $(
not including  $  v $
or  $  w $) 
such that any chain from  $  v $
to  $  w $
passes through  $  S $. 
The vertex form of Menger's theorem (Menger, 1928) now says that the maximum number of vertex-disjoint chains connecting distinct non-adjacent vertices  $  v $
and  $  w $
is equal to the minimal number of vertices in a  $  vw $-
separating set. Menger's theorem is closely related to the P. Hall marriage theorem; cf. [[Combinatorial analysis|Combinatorial analysis]] for that theorem.

====References====
<table>
<TR><TD valign="top">[a1]</TD> <TD valign="top">  W.T. Tutte,   "Connectivity in graphs" , Oxford Univ. Press  (1966) {{ZBL| 0146.45603}}</TD></TR>
<TR><TD valign="top">[a2]</TD> <TD valign="top">  R.J. Wilson,   "Introduction to graph theory" , Longman  (1985)</TD></TR>
<TR><TD valign="top">[a3]</TD> <TD valign="top">  H.-J. Walther,   "Ten applications of graph theory" , Reidel  (1984)  pp. Sect. 6.1</TD></TR>
</table>

[[Category:Graph theory]]