Lagmental Vicfred

Menger Equates Disjoint Paths with Minimum Separators by Vicfred

Last updated: Sat 11 February 2017

tags: mathematics, connectivity, bridges, Menger theorem

The maximum number of internally vertex-disjoint paths equals the minimum number of internal vertices separating two nonadjacent vertices. The point is to make the formal expression readable enough to audit line by line.

Objects and notation

Connectivity asks how many vertices or edges must be removed to disconnect a graph \(G\). Depth-first search timestamps \(\operatorname{tin}(v)\) and low-link values \(\operatorname{low}(v)\) expose local cut structure.

$$ \kappa(u,v)=\max\{\text{internally vertex-disjoint }u\text{--}v\text{ paths}\} $$

There are two layers here: the object \(\mathsf D\) and the law \(\mathsf C\). Writing them separately makes the direction of \(\Longrightarrow\) visible and keeps an accidental converse from slipping in.

$$ \kappa(u,v)=\min\{|S|:u,v\text{ disconnected in }G-S\} $$

Push the symbols

This is the algebraic core of the note. Once this line is correct, the surrounding interpretation has something solid to refer to.

$$ \begin{array}{c}\text{split }x\text{ into }x_{\mathrm{in}}\to x_{\mathrm{out}}\text{ of capacity }1\\\Downarrow\\\text{vertex-disjoint paths become an integral max flow}\end{array} $$

Structural reading

The aligned summary deliberately puts the datum and conclusion on different rows. Mathematically, this is the distinction between specifying an object and proving a property of it.

$$ \begin{aligned} \mathsf{D}\;&:\quad \kappa(u,v)=\max\{\text{internally vertex-disjoint }u\text{--}v\text{ paths}\},\\[5pt] \mathsf{C}\;&:\quad \kappa(u,v)=\min\{|S|:u,v\text{ disconnected in }G-S\}. \end{aligned} $$

A hypothesis worth keeping

Bridge and articulation criteria depend on DFS-tree relationships. Applying them to an arbitrary spanning tree gives false positives.

$$ \boxed{\begin{gathered} \text{compact conclusion}\\[-2pt] \kappa(u,v)=\min\{|S|:u,v\text{ disconnected in }G-S\} \end{gathered}} $$

The important habit is to remember what was fixed before the calculation began and what was proved only afterward. The final display preserves that order.

This article was posted on Sat 27 September 2014. Facts and circumstances may have changed since publication.
Please contact me before jumping to conclusions if something seems wrong or unclear.