Proof that there there is no method to divide students into 3 groups

Question

There are 10 students in a class:

These are the pairs that like to talk together in class:

Proof that there is no method to divide 10 students into 3 groups so that each group does not have a pair that likes to talk together.

I tried to use contradiction: Suppose that there are a way to do this. 10 students would be divided into 3 groups as such

3 - 3 - 4

I also notice that each student likes to talk to three other students

But i'm stuck here and don't know what to do next

Just checked that there are a total of 20 solutions. Four for each of the five groups of four people that we can group together. — AnilCh, Jul 26 '21 at 09:20

score 1 · Accepted Answer · answered Jul 26 '21 at 08:04

1

How about:

answered Jul 26 '21 at 08:04

JMP

Could you tell me how you got this answer – Kain Jul 26 '21 at 08:11
I forced a 4-group with Michael, and picked Chris because they both like Daniel. The rest was luck. – JMP Jul 26 '21 at 08:14

1 Answers1