Two Rooms Seven Talks

A conference has 7 talks, A through G. These pairs conflict and cannot share a room:

A-B, B-C, C-D, D-E, E-A, F-G, A-F

You have exactly 2 rooms and no time slots: every talk runs at once. Can you split the 7 talks so that no conflicting pair shares a room?

A

No, because 7 is odd, so the talks cannot be divided into two equal sides.

B

No. A-B-C-D-E-A is a cycle of length 5, and a graph is 2-colourable exactly when every cycle has even length.

C

Yes: {A, C, G} in room 1 and {B, D, E, F} in room 2.

D

No, because talk A conflicts with three other talks and there are only two rooms.