Well I did say that this is a well worn graph theory question,

I suggest that you consider a scaled down problem.

Say you and your mate have two other couples in.

That is six people and you find the others have exchanged

handshakes.

Draw that graph. Pick the one with four handshakes (draw it out).

There is no edge from that vertex to one of the other five vertices. He/she must be partners with the zero vertex.

Move to another vertex of degree three, Draw those edges. Which one is this a partner?

Which vertex are you? Which is your roommate?