Vertex separator
In graph theory, a vertex subset  is a vertex separator (or vertex cut, separating set) for nonadjacent vertices  and  if the removal of  from the graph separates  and  into distinct connected components. Examples

Consider a grid graph with  rows and  columns; the total number  of vertices is . For instance, in the illustration, , , and . If  is odd, there is a single central row, and otherwise there are two rows equally close to the center; similarly, if  is odd, there is a single central column, and otherwise there are two columns equally close to the center. Choosing  to be any of these central rows or columns, and removing  from the graph, partitions the graph into two smaller connected subgraphs  and , each of which has at most  vertices. If  (as in the illustration), then choosing a central column will give a separator  with  vertices, and similarly if  then choosing a central row will give a separator with at most  vertices. Thus, every grid graph has a separator  of size at most  the removal of which partitions it into two connected components, each of size at most . To give another class of examples, every free tree  has a separator  consisting of a single vertex, the removal of which partitions  into two or more connected components, each of size at most . More precisely, there is always exactly one or exactly two vertices, which amount to such a separator, depending on whether the tree is centered or bicentered. As opposed to these examples, not all vertex separators are balanced, but that property is most useful for applications in computer science, such as the planar separator theorem. Minimal separators
Let  be an -separator, that is, a vertex subset that separates two nonadjacent vertices  and . Then  is a minimal -separator if no proper subset of  separates  and . More generally,  is called a minimal separator if it is a minimal separator for some pair  of nonadjacent vertices. Notice that this is different from minimal separating set which says that no proper subset of  is a minimal -separator for any pair of vertices . The following is a well-known result characterizing the minimal separators: 

Lemma. A vertex separator  in  is minimal if and only if the graph , obtained by removing  from , has two connected components  and  such that each vertex in  is both adjacent to some vertex in  and to some vertex in . The minimal -separators also form an algebraic structure: For two fixed vertices  and  of a given graph , an -separator  can be regarded as a predecessor of another -separator , if every path from  to  meets  before it meets . More rigorously, the predecessor relation is defined as follows: Let  and  be two -separators in . Then  is a predecessor of , in symbols , if for each , every path connecting  to  meets . It follows from the definition that the predecessor relation yields a preorder on the set of all -separators. Furthermore,  proved that the predecessor relation gives rise to a complete lattice when restricted to the set of minimal -separators in . See also

 Chordal graph, a graph in which every minimal separator is a clique. k-vertex-connected graph

Notes

References

. . Graph connectivity