# Graph, connectivity of a

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$.