Let a transversal be defined as an independent set of $G$, containing precisely one vertex from each $V_i$. Let $G = (V,E)$ be a cycle of length $4n$ and let $V = V_1 \cup V_2 \cup \ldots \cup V_n$ be a partition of its $4n$ vertices into $n$ pairwise disjoint subsets, each of cardinality 4. Is it true that there exists a transversal on $G$?



You must log in to answer this question.

Browse other questions tagged .