# Graph Theory/k-Connected Graphs

Definition of connectedness

Let u and v be a vertex of graph ${\displaystyle G}$.

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

The minimum number of edges lambda(${\displaystyle G}$) whose deletion from a graph ${\displaystyle G}$ disconnects ${\displaystyle 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(${\displaystyle G}$) whose deletion from a graph ${\displaystyle G}$ disconnects it.

Let lambda(${\displaystyle G}$) be the edge connectivity of a graph ${\displaystyle G}$ and delta(${\displaystyle G}$) its minimum degree, then for any graph,
kappa(${\displaystyle G}$) ≤ lambda(${\displaystyle G}$) ≤ delta(${\displaystyle 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 ${\displaystyle u}$ and ${\displaystyle v}$ (the minimum number of edges whose removal disconnects ${\displaystyle u}$ and ${\displaystyle v}$) is equal to the maximum number of pairwise edge-disjoint paths from ${\displaystyle u}$ to ${\displaystyle v}$

• vertex connectivity

The size of the minimum vertex cut for ${\displaystyle u}$ and ${\displaystyle v}$ (the minimum number of vertices whose removal disconnects ${\displaystyle u}$ and ${\displaystyle v}$) is equal to the maximum number of pairwise vertex-disjoint paths from ${\displaystyle u}$ to ${\displaystyle 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 ${\displaystyle u}$ and ${\displaystyle v}$ in a graph ${\displaystyle G}$ is exactly the weight of the smallest set of edges to disconnect ${\displaystyle G}$ with ${\displaystyle u}$ and ${\displaystyle v}$ in different components.

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