# Vertex separator

In graph theory, a vertex subset is a **vertex separator** for nonadjacent vertices and if the removal of from the graph separates and into distinct connected components.

## Examples

Consider a grid graph with *r* rows and *c* columns; the total number *n* of vertices is *r*c*. For instance, in the illustration, *r* = 5, *c* = 8, and *n* = 40. If *r* is odd, there is a single central row, and otherwise there are two rows equally close to the center; similarly, if *c* is odd, there is a single central column, and otherwise there are two columns equally close to the center. Choosing *S* to be any of these central rows or columns, and removing *S* from the graph, partitions the graph into two smaller connected subgraphs *A* and *B*, each of which has at most *n*/2 vertices. If *r* ≤ *c* (as in the illustration), then choosing a central column will give a separator *S* with *r* ≤ √*n* vertices, and similarly if *c* ≤ *r* then choosing a central row will give a separator with at most √*n* vertices. Thus, every grid graph has a separator *S* of size at most √*n*, the removal of which partitions it into two connected components, each of size at most *n*/2.^{[1]}

To give another class of examples, every free tree *T* has a separator *S* consisting of a single vertex, the removal of which
partitions *T* into two or more connected components, each of size at most *n*/2. 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.^{[2]}

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 *S* be an *(a,b)*-separator, that is, a vertex subset that separates two nonadjacent vertices *a* and *b*. Then *S* is a *minimal (a,b)-separator* if no proper subset of *S* separates *a* and *b*. More generally, *S* is called a *minimal separator* if it is a minimal separator for some pair *(a,b)* of nonadjacent vertices. The following is a well-known result characterizing the minimal separators:^{[3]}

**Lemma.** A vertex separator *S* in *G* is minimal if and only if the graph , obtained by removing *S* from *G*, has two connected components and such that each vertex in *S* is both adjacent to some vertex in and to some vertex in .

The minimal separators also form an algebraic structure: For two fixed vertices *a* and *b* of a given graph *G*, an *(a,b)*-separator *S* can be regarded as a *predecessor* of another (a,b)-separator *T*, if every path from *a* to *b* meets *S* before it meets *T*. More rigorously, the predecessor relation is defined as follows: Let *S* and *T* be two *(a,b)*-separators in 'G'. Then *S* is a predecessor of *T*, in symbols , if for each , every path connecting *x* to *b* meets *T*. It follows from the definition that the predecessor relation yields a preorder on the set of all *(a,b)*-separators. Furthermore, Template:Harvtxt proved that the predecessor relation gives rise to a complete lattice when restricted to the set of *minimal* *(a,b)*-separators in *G*.

## See also

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

## Notes

- ↑ Template:Harvtxt. Instead of using a row or column of a grid graph, George partitions the graph into four pieces by using the union of a row and a column as a separator.
- ↑ Template:Harvtxt
- ↑ Template:Harvtxt.

## References

- Template:Cite doi
- {{#invoke:citation/CS1|citation

|CitationClass=citation }}.

- {{#invoke:citation/CS1|citation

|CitationClass=citation }}.

- {{#invoke:Citation/CS1|citation

|CitationClass=journal }}