On the Number of Minimal Separators in Graphs

Serge Gaspers, Simon Mackenzie

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+\sqrt{5})/2{)}^{n}n)$. We prove that t…