# Graph Theory: matching question.

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.

-

It doesn't even seem to be true. Suppose the students are Adam, Brian, Charles, Dan, Eric and Fred:

• Adam, Brian and Charles are friends and each prefers the two others.
• Dan, Eric and Fred are friends and each prefers the two others.

Since each friend clique has an odd number of students in them, at least one room has to be shared by students from different cliques -- but those will not have preferred each other.

-
Turns out there was a mistake in the question. Your solution found that mistake. – Relative0 Jun 8 '13 at 17:01