Skip to main content
3 of 3
added 173 characters in body
Brendan McKay
  • 37.7k
  • 3
  • 80
  • 147

Consider a graph $G$ with $g(n)$ edges. $G$ has average degree $2g(n)/n$ so there is a vertex $v$ with degree at most $$\delta = \left\lfloor \frac{2g(n)}{n}\right\rfloor.$$ Since by assumption $G-v$ has the property, $g(n-1) \ge g(n)-\delta$. Now solve this inequality for $g(n)$.

Write $2g(n)=an+b$ for $0\le b\le n-1$, then you can expand the floor and solve for $a$. Put that back into $an+b$ and you get (for $n\ge 3$) $$ g(n) \le \frac{n g(n-1)-b}{n-2},$$ which implies the given inequality.

You might think that the $-b$ in the last numerator allows for a slightly tighter inequality, but I think it doesn't. At the moment I have forgotten the reasoning there.

Brendan McKay
  • 37.7k
  • 3
  • 80
  • 147