Cut-set lattices of graphs

Summary

Let G be a connected, undirected, simple graph. Let V(G) and E(G) denote the vertex and edge sets respectively. Consider two different vertices a, b of G. A subset T of the vertex (edge) set is called an a, b-vertex (edge) cut if T separates a and b but no proper subset T' of T does, i. e. if in G - T the vertices a and b belong to different connected components but in G - T' there is always an a, b path. Cuts with the smallest cardinality are called minimal.

Let now S, T be two a, b-vertex (edge) cuts and order them in such a way that S ≦ T if and only if no a, b-path meets T ‘before’ S. Then it can be shown that ≦ is a partial order; indeed we have (for proofs see for example [1]):

Theorem 1.Let Γ₁and Γ₂be the sets of all a, b-vertex cuts and a, b-edge cuts, respectively, of a graph G with respect to two different, fixed vertices a, b of G. Then (Γ₁, ≦) and (Γ₂, ≦) constitute complete lattices.

Theorem 2.Let Δ₁and Δ₂be the sets of all minimal a, b-vertex cuts and minimal a, b-edge cuts, respectively, of a graph G with respect to two different, fixed vertices a, b of G. If the cardinality of the cuts is finite, then (Δ₁, ≦) and (Δ₂, ≦) constitiite distributive lattices.