Menger's theorems on local-connectivity (directed and undirected graphs). Definitions of k-connected, k-edge-connected, K(G) and X(G), Menger's theorems (without proof for the vertex version), relation between K(G), X(G) and 8(G).

Menger's Theorem — Local Edge-Connectivity (Directed) (!!!)

Given a directed graph G with two vertices s, t ∈ V(G) and k ∈ ℕ, the following are equivalent: There are k edge-disjoint st-paths. There is no (s, t)-disconnecting set of edges of size k − 1. The network (G, s, t, c) with c(e) = 1 for all e ∈ E(G) has a flow of value at least k.

Menger's Theorem — Local Edge-Connectivity (Undirected) (!!!)

Given an undirected graph G with two vertices s, t ∈ V(G) and k ∈ ℕ, the following are equivalent: There are k edge-disjoint st-paths. There is no (s, t)-disconnecting set of edges of size k − 1. The network (G, s, t, c) with c(e) = 1 for all e ∈ E(G) has a flow of value at least k. For undirected graphs, each edge is replaced by two directed edges of capacity 1 in both directions.

Menger's Theorem — Local Vertex-Connectivity (Directed) (!!!)

Given a directed graph G with two non-adjacent vertices s, t ∈ V(G) and k ∈ ℕ, the following are equivalent: There are k vertex-disjoint st-paths. There is no (s, t)-disconnecting set of vertices of size k − 1. The network (G, s, t, c) with c(e) = 1 for all e ∈ E(G) and c(v) = 1 for all v ≠ s, t has a flow of value at least k.

Menger's Theorem — Local Vertex-Connectivity (Undirected) (!!!)

Given an undirected graph G with two non-adjacent vertices s, t ∈ V(G) and k ∈ ℕ, the following are equivalent: There are k vertex-disjoint st-paths. There is no (s, t)-disconnecting set of vertices of size k − 1. The network (G, s, t, c) with c(e) = 1 for all e ∈ E(G) and c(v) = 1 for all v ≠ s, t has a flow of value at least k. For undirected graphs, each edge is additionally replaced by two directed edges, and each vertex v is split into vᵢₙ and vₒᵤₜ with a directed edge of capacity 1 between them.

k-Connected / k-Vertex-Connected (!!!)

A graph G is said to be k-connected (or k-vertex-connected) if it has more than k vertices and deleting any k − 1 vertices does not disconnect it.

k-Edge-Connected (!!!)

A graph G is said to be k-edge-connected if deleting any k − 1 edges does not disconnect it.

κ(G) — Vertex Connectivity (!!!)

κ(G), the vertex connectivity number of G, is defined as the largest k for which G is k-vertex-connected. Note: κ(Kₙ) = n − 1, since you must remove all other vertices to disconnect a complete graph.

λ(G) — Edge Connectivity (!!!)

λ(G), the edge connectivity number of G, is defined as the largest k for which G is k-edge-connected.

Menger's Theorems for Connectivity (!!!)

For any graph G and any k ≥ 1: G is k-edge-connected if and only if there are k edge-disjoint paths between any two distinct vertices. G is k-connected (k-vertex-connected) if and only if G has at least k + 1 vertices and there are k vertex-disjoint paths between any two distinct vertices.

Relation Between κ(G), λ(G) and δ(G) (!!!)

For any graph G: κ(G) ≤ λ(G) ≤ δ(G). Removing all edges incident on a minimum degree vertex disconnects the graph, so λ(G) ≤ δ(G). If there are k vertex-disjoint paths between every pair of vertices, there are also k edge-disjoint paths, so κ(G) ≤ λ(G). ( κ(G) ≤ λ(G) ≤ δ(G)