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 2.5.1. While this may yield a good lower bound, sometimes it will give us a trivial $\Omega$(1) lower bound.