There are 10 students in class. Every student sent an email to exactly 5 of them. At least how many people who sent emails to each other?

My approach : consider 10 vertices as 10 students and edges representing the emails

so complete graph with 10 vertices have 45 edges

now changing all undirected edges to directed there will still be no 2 students who are sending emails to each other because we changed undirected to directed so there are no cycles between vertices of length 2.

Now we got 5 remaining edges or emails to send as soon as we'll add these 5 directed edges, we'll get 6 more people at minimum.

Am i going wrong somewhere because answer given is 5.

  • $\begingroup$ Can you rephrase the third sentence ? It doesn’t make much sense. $\endgroup$ – Kantura Nov 8 '18 at 19:33
  • 1
    $\begingroup$ Do you mean "at least how many pairs of people have sent emails to each other"? Because if A and B exchange emails and A and C exchange emails, we cannot say that $3$ people have sent emails to each other as B and C have not done so. $\endgroup$ – Jens Nov 8 '18 at 22:45
  • $\begingroup$ Can you please rephrase the question? Do you mean "At least how many pairs of people sent emails to each other" or something like that? $\endgroup$ – YiFan Nov 9 '18 at 8:40
  • $\begingroup$ I got the exact same question in a work book. Now i'm also confused how to interpret. $\endgroup$ – Mk Utkarsh Nov 9 '18 at 10:41

Assuming the question is "What is the minimum number of pairs of students who sent emails to each other?", there must be at least $5$ pairs of students who sent emails to each. There are $\binom{10}{2}=45$ pairs of students, meaning that if we must distribute $10*5=50$ edges among $45$ pairs, then by the pigeonhole principle there must be at least $5$ pairs with $2$ emails. To finish the proof that this is the maximum lower bound, we can construct a graph with $50$ directed edges with exactly $5$ pairs with $2$ emails between them. This is not difficult, so I leave it to you.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.