Skip to main content
2 of 2
Capitalise title
LSpice
  • 12.9k
  • 4
  • 45
  • 69

Maximal graphs with a property that is invariant w.r.t. vertex removal

Let $P$ be a property of graphs such that if a graph $G$ has $P$, then any graph obtained from $G$ by removal of a vertex also has $P$.

Let $g(n)$ be the maximum size of a graph of order $n$ having $P$. It can be shown that for $n>2$, $$g(n) \leq \left\lfloor \frac{n}{n-2}\cdot g(n-1)\right\rfloor.$$ I suspect this inequality is well known, and would like to have a reference rather than proving it from scratch. Any pointers will be appreciated!

Max Alekseyev
  • 34.3k
  • 5
  • 74
  • 152