Reducing 3-coloring problem to trio representatives


A group of students is divided into trios – groups of 3 members. Each student can be assigned to more than more trio. We want to assign their representatives, by choosing exactly one member of each trio. Is such assignment possible?

My goal is to use polynomial-time reductions to transform 3-coloring of a graph into this problem. However, I’m stuck on the correct representation.

  • If each vertex is a different student and edges represent being in the same trio, how do I separate trios?

  • If each node represents a trio, what could be a sensible meaning of the edges?

I suspect that since a 4-clique has no adequate 3-coloring (which could also mean that 4 trios with the same three members have no possible representative assignment), the latter option could be more sensible, but I’m not sure on how to proceed with this reduction proof.