prove or supply counter example about graph

Let $G = (V, E)$ be a cycle of length $4n$ and let $V = V_1 \cup V_2 \cup … \cup V_n$ be a
partition of its $4n$ vertices into n pairwise disjoint subsets, each of cardinality
4. Is it true that there must be an independent set of $G$ containing precisely
one vertex from each $V_i$? (Prove or supply a counter example.)

I think this is not right because just consider square with four vertices and four edges,but I have doubt that it is proper counter example.please help with your knowledge,thank you very much.

actually this is exercise 4 of chapter 5 from alon spencer probabilistic method.so I also tag this question as mentioned.

Solutions Collecting From Web of "prove or supply counter example about graph"

I know this is an old question, but I’m writing up solutions to Alon and Spencer, so I thought I’d supply an answer for whomever comes across this in the future


We prove the statement is true. Let $V_i = \{v_i^{(1)},v_i^{(2)},v_i^{(3)},v_i^{(4)}\}$. Pick a set $S$ by randomly choosing from each $V_i$ one vertex, uniformly and independently. Define $A_{i,k;j,l}$ to be the event that $v_i^{(k)}$ and $v_j^{(l)}$ are both in $S$ and adjacent. Now, define \begin{equation*}
x_{i,k;j,l} = \left\{ \begin{array}{ll}
0 &\quad\text{ if } v_{i}^{(k)} \text{ and } v_{j}^{(l)} \text{ are not adjacent.} \\
\frac{1}{2} &\quad\text{ if } v_{i}^{(k)} \text{ and } v_{j}^{(l)} \text{ are adjacent.}
\end{array} \right.
\end{equation*}
Let $i,j,k,l$ s.t. $v_i^{(k)}$ and $v_{j}^{(l)}$ are not adjacent. Then \begin{equation*}
\mathbb{P}[A_{i,k;j,l}] = 0 \leq 0 = x_{i,k;j,l} \prod (1 – x_{i’,k’;j’,l’}).
\end{equation*}
If $v_i^{(k)}$ and $v_{j}^{(l)}$ are adjacent, then there are only two vertices adjacent to either of the two vertices, implying that \begin{equation*}
\mathbb{P}[A_{i,k;j,l}] = \frac{1}{16} \leq \frac{1}{2}\cdot \left(\frac{1}{2}\right)^2 = x_{i,k;j,l} \prod\limits_{(i’,k’;j’,l’) \sim (i,k;j,l)} (1 – x_{i’,k’;j’,l’}).
\end{equation*}
Thus the hypotheses of the local lemma are satisfied, implying that there is a choice of $S$ that is an independent set.