Editing Vertex separator (section)

==Minimal separators==
Let {{mvar|S}} be an {{math|(''a'',''b'')}}-separator, that is, a vertex subset that separates two nonadjacent vertices {{mvar|a}} and {{mvar|b}}. Then {{mvar|S}} is a ''minimal'' {{math|(''a'',''b'')}}-''separator'' if no proper subset of {{mvar|S}} separates {{mvar|a}} and {{mvar|b}}. More generally, {{mvar|S}} is called a ''minimal separator'' if it is a minimal separator for some pair {{math|(''a'',''b'')}} of nonadjacent vertices. Notice that this is different from ''minimal separating set'' which says that no proper subset of {{mvar|S}} is a minimal {{math|(''u'',''v'')}}-separator for any pair of vertices {{math|(''u'',''v'')}}. The following is a well-known result characterizing the minimal separators:<ref>{{harvtxt|Golumbic|1980}}.</ref> 

'''Lemma.''' A vertex separator {{mvar|S}} in {{mvar|G}} is minimal if and only if the graph {{math|''G'' – ''S''}}, obtained by removing {{mvar|S}} from {{mvar|G}}, has two connected components {{math|''C''{{sub|1}}}} and {{math|''C''{{sub|2}}}} such that each vertex in {{mvar|S}} is both adjacent to some vertex in {{math|''C''{{sub|1}}}} and to some vertex in {{math|''C''{{sub|2}}}}.

The minimal {{math|(''a'',''b'')}}-separators also form an [[algebraic structure]]: For two fixed vertices {{mvar|a}} and {{mvar|b}} of a given graph {{mvar|G}}, an {{math|(''a'',''b'')}}-separator {{mvar|S}} can be regarded as a ''predecessor'' of another {{math|(''a'',''b'')}}-separator {{mvar|T}}, if every path from {{mvar|a}} to {{mvar|b}} meets {{mvar|S}} before it meets {{mvar|T}}. More rigorously, the predecessor relation is defined as follows: Let {{mvar|S}} and {{mvar|T}} be two {{math|(''a'',''b'')}}-separators in {{math|G}}. Then {{mvar|S}} is a predecessor of {{mvar|T}}, in symbols <math>S \sqsubseteq_{a,b}^G T</math>, if for each {{math|''x'' ∈ ''S'' \ ''T''}}, every path connecting {{mvar|x}} to {{mvar|b}} meets {{mvar|T}}. It follows from the definition that the predecessor relation yields a [[preorder]] on the set of all {{math|(''a'',''b'')}}-separators. Furthermore, {{harvtxt|Escalante|1972}} proved that the predecessor relation gives rise to a [[complete lattice]] when restricted to the set of ''minimal'' {{math|(''a'',''b'')}}-separators in {{mvar|G}}.