# 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.

Relevant topics on |

Graph connectivity |
---|

## 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. Notice that this is different from *minimal separating set* which says that no proper subset of *S* is a minimal *(u,v)*-separator for any pair of vertices *(u,v).* 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 "(a,b)"-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, Escalante (1972) 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

- George (1973). 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.
- Jordan (1869)
- Golumbic (1980).

## References

- Escalante, F. (1972). "Schnittverbände in Graphen".
*Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg*.**38**: 199–220. doi:10.1007/BF02996932. - George, J. Alan (1973), "Nested dissection of a regular finite element mesh",
*SIAM Journal on Numerical Analysis*,**10**(2): 345–363, doi:10.1137/0710032, JSTOR 2156361. - Golumbic, Martin Charles (1980),
*Algorithmic Graph Theory and Perfect Graphs*, Academic Press, ISBN 0-12-289260-7. - Jordan, Camille (1869). "Sur les assemblages de lignes".
*Journal für die reine und angewandte Mathematik*(in French).**70**(2): 185–190. - Rosenberg, Arnold; Heath, Lenwood (2002).
*Graph Separators, with Applications*. Springer. doi:10.1007/b115747.