An independent set S of a graph $G = (V,E)$ is any subset of vertices $S \subseteq V$ whereby no vertices in S are adjacent.
(a) List all of the largest independent sets in $C_2, C_4, C_5,~and~C_6$.
$$C_2 = \{\{V_1\}, \{V_2\}\}$$
$$C_4 = \{\{V_1, V_4\}, \{V_2, V_3\}\}$$
$$C_5 = \{\{V_1, V_3\}, \{V_1, V_4\}, \{V_2, V_4\}, \{V_2, V_5\}, \{V_3, V_5\}\}$$
$$C_6 = \{\{V_2, V_4\}, \{V_3, V_5\}, \{V_4, V_6\}\}$$
(b) Prove that the size of the largest independent sets of $C_n$ is n/2 when n is even.
If I did (a) correctly, clearly the number of the largest independent set of $C_n$ where n is even is n/2; however I know that is not an actual proof, so how would one prove this?
Best Answer
For a cycle graph $C_n$ with even $n$, for convenience, denote the set of vertices as $\{v_1, v_2, \cdots, v_n\}$ and without loss of generality, let the set of edges be $\{(v_1, v_2), (v_2, v_3), \cdots, (v_{n-1}, v_n), (v_n, v_1)\}$.
First, observe that $\{v_1, v_3, \cdots, v_{n-1}\}$ is of size $\frac{n}{2}$ and it is an independent set. Therefore, the size of the maximum independent set, denoted as $\alpha(C_n)$, is at least $\frac{n}{2}$. Now suppose that $\alpha(C_n) > \frac{n}{2}$. Since each vertex is of degree $2$ and vertices in an independent set share no edge, we conclude that there are at least $\alpha(C_n) \cdot 2 > n$, which is a contradiction.