# Restricted independent set of the cycle graph $C_{3n}$

Let $$V$$ be the vertices of the cycle graph $$C_{3n}$$. Suppose there is a partition of $$V$$ into sets of $$3$$, i.e. $$V=\cup_{k=1}^{n}{V_k}$$ where $$|V_k|=3$$ for $$k$$ in $$1..n$$.

QUESTION: Is it possible to find an independent set of $$V$$ with exactly one vertex from each $$V_k$$?

By the Lovasz Local Lemma, it's possible if the $$3$$ is replaced with some larger number, say, $$11$$.

• How could this be possible, I mean what if three vertices in a partition were adjacent to each other? Are there any conditions on the partitions $V_k$? – vidyarthi May 14 '19 at 11:21
• If they are mutually adjacent, it follows that $n=1$, so it is still possible (just choose any vertex). – LeechLattice May 14 '19 at 11:26
• any vertex is adjacent to exactly two other vertices, as there are $3$ vertices, therefore one vertex from any part would be definitely non-adjacent to at least one vertex from any other part. Thus, we can choose one vertex from each part which are independent of each other – vidyarthi May 14 '19 at 11:32
• @vidyarthi I don't think that's a proof. As vertices are added to the independent set, you can come to a part where each of the three vertices is adjacent to a vertex already in the independent set. – Brendan McKay May 14 '19 at 13:13