Show that for all graphs, $\alpha(G)\geq\sum_{v\in V(g)}(d(v)+1)^{-1}$, where $d(v)$ is the degree of the vertex, $V(G)$ is the vertex set of $G$, and $\alpha(G)$ is the cardinality of the biggest $k-clique$ in the complement of $G$.
I tried to use induction on $|V(G)|$, on $\alpha(G)$, on $\delta(G)$ and tried to use bounds like $\alpha(G)\geq \lceil\frac{n}{\chi(G)}\rceil$, but without results. Maybe working on Random Graphs could work, but I don't know what random variable should I use (I prefer solutions without using probability, for now).
We need to show an existence. With your distaste for probabilistic methods, that means we should try to construct a large enough anti-clique. How? One element at a time.
Start with a vertex $v_1$ of minimal degree $d$ in $G$. Now, nothing else in our anti-clique can have an edge to $v_1$, so we'll cut $G$ down to a new graph $G_1$ by removing $v_1$ and all of the vertices that are linked to it. What does this do to the sum $S(G)=\sum_{v\in V(G)}(d(v)+1)^{-1}$? Each $w$ removed had at least $d$ edges, so we subtract at most $\frac1{d+1}$ for each of the $d+1$ vertices removed. The remaining vertices may have had some of their edges removed, which then increases the sum. So, then, $S(G_1) \ge S(G)-1$.
That's basically what we need; we can keep going until we run out of vertices and $S$ hits zero (at least $S(g)$ steps), or we can use induction, applying the result on the graph $G_1$ with fewer vertices.
The key to making this work was that one innocuous line - choose a vertex of minimal degree. It's common sense to avoid vertices with too many edges, and it turns out going to the extreme is exactly what we need.