Is it the case that for each integer $r \geq 2$ the graph $K_{r, r}$ does not admit such a partition? Let $\{V_1, V_2\}$ be a bipartition of $K_{r, r}$. Without loss of generality let $v \in V_1$. Then $v$ and all vertices in $V_2$ must occur in one part of the partition, leaving us with an independent set $V_1 - \{v\}$.
user50739
- 1
- 1