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$?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.