Why is it not possible, in a group of 89 people, for everyone to exchange phone numbers with exactly three other people? Is there a rule in graph theory that prohibits this from being possible? I was thinking of something along the lines of Euler's theorem that talks about the degrees of vertices and how it's impossible for a graph to have an Euler path if more than two vertices have an odd degree.
 A: Let $N=\{N_j:1\leq j< K\}$ be the $K$ distinct nodes of a graph $G.$ Let $d(N_j)$ be the degree of $N_j$ in $G.$ Let $E$ be the number of edges of $G$ . Then $$2E=\sum_{j=1}^Kd(N_j).$$ Because in the summation above, any edge joining any $N_i$ to any $N_j$ is counted twice: Once as one of the $d(N_1)$ edges containing $N_i,$ and once again as one of the $d(N_j)$ edges containing $N_j.$
So if $K$ is odd it is impossible for every $d(N_i)$ to be odd. In particular if $K=89,$ we cannot have $d(N_i)=3$ for every $i.$
A: If Person A and Person B exchange numbers, then:


*

*Person A gives their number to Person B, and

*Person B gives their number to Person A.


I.e., they come in pairs.  Therefore, no matter how many people have exchanged numbers, "someone giving their phone number to someone else" occurs an even number of times.

...in a group of 89 people, for everyone to exchange phone numbers with exactly three other people.

In this scenario "someone giving their phone number to someone else" occurs $89 \times 3$ times, which is an odd number of times.

In graph terminology, the tool is the Handshaking Lemma.  In a undirected graph, these are equal:


*

*the number of edge-endpoints,

*$2 \times$ the number of edges, and

*the sum of the vertex degrees.


The second point implies the number is even.
If we attempt to draw a graph of 89 vertices each with degree 3, we find the sum of the vertex degrees is $89 \times 3$ which is odd, giving a contradiction.
A: Let's say we take 5 people instead of 89 and draw the corresponding graph such that every person exchanges phone number with 2 others and we obtain graph 1 (which is an odd cycle  $C_{5}$). Then we add edges to the graph so that every  person exchanges phone number with 3 others. We start by adding an edge between person 1 and person 3; now both 1 and 3 exchange phone numbers with 3 other people (graph 2). We do the same with person 2 and add an edge between 2 and 4; now both 2 and 4 exchange phone numbers with 3 other people (graph 3). Let's try the same with person 5. This time it's a little different, if we add an edge between 5 and 1, this means 1 would exchange numbers with 4 other people and similarly, if we add an edge between 5 and 2, it means that 2 exchanges numbers with 4 other people (graph 4). This is because we have an odd number of vertices as explained by @Rebecca J. Stones and @DanielWainfleet.

