Non-trivial Monotone Graph Properties

For a non-trivial monotone graph property $p$, there exists some $a < b$ such that the property holds for all graphs with $b$ edges, but not for any graph with $a$ edges. We can therefore apply Theorem . While this may yield a good lower bound, sometimes it will give us a trivial $\Omega(1)$ lower bound.