Is it possible in a group of seven people for each to be friends with exactly 3 others?
I know that the sum of degrees of vertices in a graph must be even.
$\endgroup$ 33 Answers
$\begingroup$Let $G(V,E)$ represent our graph. Because we know every person must be friends with excatly three other people, we now: $\forall v \in V$. deg$(v) = 3$. By the hand-shaking lemma:\begin{align} 2|E| = \sum_{v \in V} deg(v) \Rightarrow 2|E| = \sum_{n=1}^7 3 = 21. \end{align}
However $|E|$ is an integer so we come to a contradiction, since we get $|E| = \frac{21}{2}.$
$\endgroup$ $\begingroup$This can be solved by considering the handshaking theorem. Which states that the degree of a graph is twice the number of edges. This means that the final degree of any graph should be even. This can be further extended that the number of odd degree vertices should be even in number for a graph to be valid. so degree can be represented as 3, 3, 3, 3, 3, 3, 3 which sums to 21 which is an odd number. So it is not a valid graph. It would have been a valid graph if there were 8 people who knew 3 people
$\endgroup$ $\begingroup$So you consider the people as vertices and friendship as edges between them. then sum of all degrees is 21 , which is a contradiction.
$\endgroup$
