Prove for all graphs $\alpha(G) \ge \displaystyle \sum_{x \ V(G)} \frac{1}{deg(x) + 1}$
$\alpha(G) :=$ maximum independent set.
I think induction is the best way to do this but I'm not sure what I should induct over, possibly $\mid V(G) \mid$ or maybe over the sum of degrees
Say over $\mid V(G) \mid$ then
Base case 1 : $\mid V(G) \mid = 1 \,\, \checkmark $ since $\alpha(G) = 1 \ge \frac{1}{2}$
Base case 2: $\mid V(G) \mid = 2 \,\, \checkmark $ since $\alpha(G) = 1 \ge 1$
IH: Assume property holds for $\mid V(G) \mid < k$
Let G be a graph on $k$ vertices
ASIDE : { On $k$ vertices (For a connected graph) $K_{1,k-1}$ has $\alpha(G) = k-1$, if G is $k$-many isolated vertices then $\alpha(G) = k$ and $K_k$ has $\alpha(G) = 0$ and further in the case of $K_k$ we get $\sum_{x \in V(G)} \frac{1}{deg(x) + 1} = \frac{1}{k-1+1}*k = 1 \le 1 = \alpha(1)$ }
Now I'm a tad stuck because I'm not sure if this is the correct way to go about it because I could delete a vertex to be able to invoke the IH but that doesn't feel informative enough to get the result.
Consider the following algorithm:
\begin{align} &\mathtt{for\ each}\ v\ \mathtt{in}\ V\ \mathtt{do} \\ &\quad \mathtt{IsMarked}[v] \gets \mathtt{false} \\ &\pi \gets \text{random permutation of }V\\ &\mathtt{for\ each}\ v\ \mathtt{in}\ \pi\ \mathtt{do}\\ &\quad\mathtt{if\ }\text{no neighbor of}\ v\ \text{is marked}\ \mathtt{then}\\ &\quad\quad \mathtt{IsMarked}[v] \gets \mathtt{true}\\ &A = \{v \in V \mid \mathtt{IsMarked}[v] = \mathtt{true}\} \end{align}
Observe that any individual vertex $v$ has $\frac{1}{\deg(v)+1}$ chance to be considered before all its neighbors, thus with at least this probability it is included in $A$. In other words, the expected size of $A$ is at least $\sum_{v \in V}\frac{1}{\deg(V)+1}$. Moreover, because of how we build $A$, it is an independent set, and its expected size has to be smaller or equal to the size of the maximum independent set in the graph.
I hope this helps $\ddot\smile$