Let $G = (V,E)$ be a connected $r-1$ regular graph such that $|V| = r*p$, where $p\geq2$. I want to see that $\alpha(G) \geq p+1$.
I've considered this approach: suppose the maximum independent set has size strictly smaller than $p+1$. We can easily form an independent set of size at least $p$, so necessarily $\alpha(G) = p$. Given $I = \{v_1,…,v_p\}$ the maximum independent set, every vertex $v_i \in I$, it is adjacent to $r-1$ other vertices in $V \setminus I$. In the worst case scenario, for every pair $v_i, v_j \in I$ we have that $N(v_i) \cap N(v_j) = \emptyset$. As a result $|V \setminus I| = p(r-1)$. Every vertex $u \in V \setminus I$ must be adjacent to other $r-1$ vertices, one of them is in $I$ and the other $r-2$ in $V \setminus I$. However I don't see how this gets me to a contradiction. What am I missing?
Best Answer
A greedy algorithm for finding a large independent set $I$ proceeds as follows:
In the worst case, this marks $r$ vertices as used every time a vertex is added to $I$, and we exhaust all $pr$ vertices in $p$ rounds; this proves $|I|\ge p$ at the end.
However, all we have to do in order to do better is make sure that at least one of the times when we do step 3 and add a vertex $u_i$ to $I$, one of the neighbors of $u_i$ has already been marked as used. In that case, we mark only $r-1$ (or fewer) vertices as used in that round, and so we won't be able to exhaust all $pr$ vertices in $p$ rounds. This means it will take us at least $p+1$ rounds, so $|I|\ge p+1$.
How do we know that we can make sure of this? Well, if we ever reach step 3 and none of the unused vertices have a used neighbor, then that means that the graph is disconnected: we can split up the vertices into two sets (the used vertices and the unused vertices) with no edges between them. We assumed that the graph is connected, so this can't happen.
In fact, we can make sure to pick a vertex with a used neighbor every time we do step 3. This means that after the first round (which marks $r$ vertices as used), we mark at most $r-1$ vertices as used in every round. This way, we only mark at most $r + (k-1)(r-1)$ vertices after $k$ rounds, and $$r + (k-1)(r-1) \ge pr \iff k \ge \frac{pr-1}{r-1}.$$ So we find an independent set of order at least $\left\lceil \frac{pr-1}{r-1}\right\rceil$ with this algorithm, which can be significantly better than $p+1$ if $p$ is large compared to $r$.
For $r > 3$, we get a very slight improvement (and a simpler argument) by citing Brooks' theorem, which tells us that the graph $G$ is $(r-1)$-colorable; by taking the largest color class, we get an independent set of size at least $\left\lceil \frac{pr}{r-1}\right\rceil$.