# Graph Theory/k-Connected Graphs

- Definition of connectedness

Let u and v be a vertex of graph .

- If there is a path in , then we say that and are
**connected**. - If there is a path for every pair of vertices and in , then we say that is connected or
**connected graph**.

- Edge Connectivity

The minimum number of edges lambda() whose deletion from a graph disconnects , 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() whose deletion from a graph disconnects it.

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

kappa() ≤ lambda() ≤ delta()

*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 and (the minimum number of edges whose removal disconnects and ) is equal to the maximum number of pairwise edge-disjoint paths from to

- vertex connectivity

The size of the minimum vertex cut for and (the minimum number of vertices whose removal disconnects and ) is equal to the maximum number of pairwise vertex-disjoint paths from to

( 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 and in a graph is exactly the weight of the smallest set of edges to disconnect with and in different components.

- maximum flow : The maximum flow between vertices and in a graph
- minimum cut : the smallest set of edges to disconnect with and in different components.