In a college dorm two students share a single room. Each student is asked to give two names of preferred roommates. Housing ensures that if a student is on the preferred list of some other student then the second student is also on the preferred list of the ﬁrst student.
Prove that it is always possible to pair the students such that everyone's roommate is from the preferred list.
So say Student A has (B,C) as preferred roommates, so B would be on the preferred list of A - now "some other student", would that mean that if there is this other student D then ???
Honestly I don't understand what the question is trying to say - how to even set this up. I do realize that this would have to do with matching - perhaps some sort of alternating graph.
Any help would be greatly appreciated.