Edge-disjoint paths, disconnecting sets of edges, vertex-disjoint paths, disconnecting set of vertices, local edge-connectivity X(x, y), X'(x,y), and local vertex-connectivity k(x, y), k'(x, y), Theorems on connection of above with network flows in directed and undirected graphs.

Edge-Disjoint Paths (!!!)

Given x, y ∈ V(G), two xy-paths are said to be edge-disjoint if they do not share any edges. Note: edge-disjoint paths may still share vertices.

Disconnecting Set of Edges / Edge Cut (!!!)

Given x, y ∈ V(G), a subset S ⊆ E(G) is called an (x, y)-disconnecting set of edges or an edge cut separating x from y, if deleting the edges in S disconnects x from y, i.e. there is no path left from x to y.

Vertex-Disjoint Paths (!!!)

Given x, y ∈ V(G), two xy-paths are said to be vertex-disjoint if they do not share any vertices except for x and y themselves.

Disconnecting Set of Vertices / Vertex Cut (!!!)

Given x, y ∈ V(G), a subset S ⊂ V(G) with x, y ∉ S is called an (x, y)-disconnecting set of vertices or a vertex cut separating x from y, if deleting the vertices in S disconnects x from y. Note: if x and y are adjacent, it is not possible to disconnect them by removing any other vertices.

Local Edge-Connectivity λ(x, y) and λ'(x, y) (!!!)

Given a graph G and two vertices x, y ∈ V(G): λ(x, y) — the size of the smallest (x, y)-disconnecting set of edges. λ'(x, y) — the maximum number of edge-disjoint xy-paths.

Menger's Theorem for Local Edge-Connectivity (!!!)

Given a graph G, for all s, t ∈ V(G) with s ≠ t: λ(s, t) = λ'(s, t). The minimum number of edges needed to disconnect s from t equals the maximum number of edge-disjoint st-paths.

Local Vertex-Connectivity κ(x, y) and κ'(x, y) (!!!)

Given a graph G and two non-adjacent vertices x, y ∈ V(G): κ(x, y) — the size of the smallest (x, y)-disconnecting set of vertices. κ'(x, y) — the maximum number of vertex-disjoint xy-paths.

Menger's Theorem for Local Vertex-Connectivity (!!!)

Given a graph G, for all s, t ∈ V(G) with s ≠ t where s and t are not adjacent: κ(s, t) = κ'(s, t). The minimum number of vertices needed to disconnect s from t equals the maximum number of vertex-disjoint st-paths.

Connection Between Local Edge-Connectivity and Network Flows (!!!)

Given a directed graph G with capacity c(e) = 1 on every edge, if there is a flow f with val(f) = d > 0 taking values 0 or 1 on every edge, then G contains d edge-disjoint paths from s to t. For any s ≠ t, 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 edges has a flow of value at least k. This holds for both directed and undirected graphs. For undirected graphs, each edge is replaced by two directed edges of capacity 1 in both directions.

Connection Between Local Vertex-Connectivity and Network Flows (!!!)

To reduce vertex-disjoint paths to a network flow problem, we apply the vertex capacity modification: each vertex v is split into vᵢₙ and vₒᵤₜ with a directed edge of capacity 1 between them. All incoming edges go to vᵢₙ and all outgoing edges leave from vₒᵤₜ. The original edges are given large capacity (not 1), so that vertices and not edges limit the flow. This enforces vertex-disjointness, and the maximum flow equals κ(x, y). For any non-adjacent s ≠ t, 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 with c(e) = 1 for all edges and c(v) = 1 for all v ≠ s, t has a flow of value at least k. This holds for both directed and undirected graphs