# Connectivity and the theorems of Menger

Definition 4..1 (Notation for subgraphs)

If graph and then is the induced subgraph with edges in deleted. Given then is the spanning subgraph obtained by deleting edges in .

Definition 4..2 ( connected)

A graph is connected if and is connected for any with .

Observation 4..3

The only connected graph with vertices is the complete graph .

Definition 4..4 (Connectivity)

The connectivity of or isconnected.

Definition 4..5 (Local connectivity)

If distinct and the local connectivity has no path , the minimum number vertices separating and .

Observation 4..6

If is not complete then , which is the same as .

If is complete then does not have a value, but .

Definition 4..7 (-edge connected)

A graph is -edge connected if is connected for all with .

Definition 4..8 (Edge connectivity )

The edge connectivity of is is edge connected.

Definition 4..9   If distinct then the local edge connectivity is has no path . Note that .

Definition 4..10 (Independent paths)   Two paths are independent if their only common vertices are .

Theorem 4..11 (Menger)

Vertex form. Let distinct. then maximum number of pairwise independent paths.

Edge form. distinct. Then maximum number of edge disjoint paths.

Proof. Vertex form. Replace all edges with two directed edges and give each vertex capacity 1. Apply vertex form of max-flow min-cut to get an integer flow from , since each vertex has capacity or 0.

Edge form. Do the same thing but use the edge form of max-flow min-cut.

Definition 4..12 (Line graph)

The line graph is the graph with a vertex for each and an edge whenever and have a common end vertex in .

Observation 4..13   The edge form can be deduced from the vertex from, using the line graph.

Observation 4..14   Given a set of independent paths then certainly , but it is not necessarily possible to add paths to to form independent paths.

Observation 4..15   There is a multiple source - sink version of Menger's theorem.

Lemma 4..16

Assume and let . Then .

Proof. Let . Choose with and disconnected. Let and be vertices in different components of , so that is minimal. Then either
1. so is disconnected; or
2. so is disconnected; or

3. so , so .

All cases imply that .

Corollary 4..17

A graph is -connected iff any two vertices are joined by at least independent paths.

Proof. If is not a complete graph, . Apply Menger's theorem.

is -connected iff , so true for a complete graph.

Corollary 4..18

A graph is -edge-connected iff any two vertices are joined by at least edge disjoint paths.

John Fremlin 2010-02-17