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

There are 10 students in a class:

1. Michael
2. Michelle
3. Jack
4. Daniel
5. James
6. Jane
7. Tom
8. Thompson
9. Chris
10. Tracy

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

1. Michael - Michelle
2. Michael - Jack
3. Michael - Daniel
4. Michelle - James
5. Michelle - Jane
6. Jane - Tom
7. Jane - Thompson
8. Thompson - Chris
9. Jack - Thompson
10. Jack - Tracy
11. Daniel - Tom
12. Daniel - Chris
13. James - Tracy
14. James - Chris
15. Tom - Tracy

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. Jul 26, 2021 at 9:20