# On the Number of Minimal Separators in Graphs

arXiv: https://arxiv.org/abs/1503.01203 · HTML: https://mlsanity.com/paper/1503.01203/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 4 Mar 2015.

## Built on by (most cited first, 1 of 1)

- [Invariant Ancestry Search](https://mlsanity.com/paper/2202.00913/) (2022)

## Abstract (arXiv)

We consider the largest number of minimal separators a graph on n vertices can have at most. We give a new proof that this number is in O( ((1+√5)/2)n n ). We prove that this number is in ω( 1.4521n ), improving on the previous best lower bound of Omega(3n/3) subseteq ω( 1.4422n ). This gives also an improved lower bound on the number of potential maximal cliques in a graph. We would like to emphasize that our proofs are short, simple, and elementary.