Graph Theory/k-Connected Graphs

Definition of connectedness

Let u and v be a vertex of graph $G$.

• If there is a $u-v$ path in $G$, then we say that $u$ and $v$ are connected.
  
• If there is a $u-v$ path for every pair of vertices $u$ and $v$ in $G$, then we say that $G$ is connected or connected graph.

Edge Connectivity

The minimum number of edges lambda($G$) whose deletion from a graph $G$ disconnects $G$, also called the line connectivity. The edge connectivity of a disconnected graph is 0, while that of a connected graph with a graph bridge is 1.

Vertex Connectivity

The minimum number of vertices kappa($G$) whose deletion from a graph $G$ disconnects it.

Let lambda($G$) be the edge connectivity of a graph $G$ and delta($G$) its minimum degree, then for any graph,
kappa($G$) ≤ lambda($G$) ≤ delta($G$)

k-connected Graph

• k-edge-connected Graph
  

A graph has edge connectivity k if k is the size of the smallest subset of edges such that the graph becomes disconnected if you delete them.

• k-vertex-connected Graph
  

A graph has vertex connectivity k if k is the size of the smallest subset of vertices such that the graph becomes disconnected if you delete them.
A 1-connected graph is called connected; a 2-connected graph is called biconnected. A 3-connected graph is called triconnected.

Menger's Theorem

• edge connectivity

The size of the minimum edge cut for $u$ and $v$ (the minimum number of edges whose removal disconnects $u$ and $v$) is equal to the maximum number of pairwise edge-disjoint paths from $u$ to $v$

• vertex connectivity

The size of the minimum vertex cut for $u$ and $v$ (the minimum number of vertices whose removal disconnects $u$ and $v$) is equal to the maximum number of pairwise vertex-disjoint paths from $u$ to $v$
( An edge cut is a set of edges whose removal disconnects the graph, and similarly a vertex cut or separating set is a set of vertices whose removal disconnects the graph. )

max-flow( maximum flow ) min-cut( minimum cut ) Theorem

The maximum flow between vertices $u$ and $v$ in a graph $G$ is exactly the weight of the smallest set of edges to disconnect $G$ with $u$ and $v$ in different components.

• maximum flow : The maximum flow between vertices $u$ and $v$ in a graph $G$
• minimum cut : the smallest set of edges to disconnect $G$ with $u$ and $v$ in different components.