Suppose that $G$ is a planar graph. What is an example of a theorem that will give us a lower bound on the size of a maximum independent set of vertices in $G$?
The following may or may not be true, but as an example, we want something like,
If $G$ has $n$ vertices, there there exists an independent set in G containing at least $n/4$ vertices.
For any graph $G$, let $\alpha(G)$ denote maximum number of vertices in an independent set in $G$.
Sometime between 1974 & 1976 Michael O'Albertson proved:
However, that very slightly pre-dated the proof of the 4-color theorem, in 1976, by Kenneth Appel and Wolfgang Haken.
A corollary of 4-color theorem is that:
$1/4 > 2/9$