Question

-Discrete math course

(10) At a table are 7 people who make a toast and touch glasses. Is it possible for each person to touch glasses with exactly 3 others? Either draw a graph showing how it can be done (edge indicating glasses touched), or explain why it can't be done.

Answer 1

Consider the graph whose vertices are the 7 people at the table. And edge is drawn between two people if and only if they touch glasses.

Then, we want it to be the case that each person has touched glasses with exactly 3 others. So that every vertex has degree 3.

Is this possible? We check the handshaking lemma which says $\sum_{v\in V}\deg(v)=2e$ (sum of degrees must be twice the number of edges)

And so, we have $\sum_{v\in V}3=2e$

And as there are 7 vertices, this equals $\sum_{v\in V}3=3\times 7=21=2e$ which is impossible because the left side is 21 which is odd and the right side is which is even

So such a case (that each person has touched glasses with exactly 3 others, is not possible)

$\blacksquare$

Please do rate this answer positively if you found it helpful. Thanks and have a good day!