# Thread: (Graph Theory) Minimum possible number of friendships

1. ## (Graph Theory) Minimum possible number of friendships

Hello. Here is the problem:
There are 2000 people on a social network. Each person sends 1000 friend requests. Two people are friends if they've sent a friend request to each other. What is the minimum possible number of friendships on this social network?

2. ## Re: (Graph Theory) Minimum possible number of friendships

Originally Posted by nkole
Hello. Here is the problem: There are 2000 people on a social network. Each person sends 1000 friend requests. Two people are friends if they've sent a friend request to each other. What is the minimum possible number of friendships on this social network?
Lets get some house-keeping out of the way. No one issues a friend to him/herself nor to the same person more that once. Now this is a directed (dirgraph) problem in which there are $2\cdot 10^3$ vertices. The out-degree, $\deg^+(v_j)=10^3$, while the in-degree, $\deg^-(v_j)\le 1999$.

Say a person is $w$ then that person issues a thousand friend requests, $\deg^+(w)=10^3$; but $w$ is also the most popular person in the group so that $w$ receives friend requests from everyone else in the gathering, $\deg^-(w)=1999$. BUT in this unlikely event there are still only one thousand friendship pairs where one person is $w$. Can you explain why? How many people like $w$ can there be (people who receive requests from everyone)?

So there are $(2\cdot 10^3)(10^3)=2\cdot 10^6=2,000,000$ requests issued. WHY?

Can you make any progress now?? If so show us your work.

3. ## Re: (Graph Theory) Minimum possible number of friendships

Another way to approach this type of problem is to try to create a situation where you think you are coming up with a minimum number of friend requests. Once you see how to actually achieve the minimum number, it becomes easier to prove that you found the minimum number (of course, you have to be careful that you don't start off with the assumption that you are correct, or your proof will not succeed).

Example: Number the people 1 through 2000. Each person contacts the first thousand people who are all numbered as low as possible (such that person 1 friend requests people 2 through 1001, person 2 sends requests to persons 1 and 3 through 1001, etc.) This is not a proof that this generates the minimum number of friendships, but hopefully it helps you see one way that it can occur. Once you complete Plato's proof, you should see that this does, in fact, produce the minimum possible number of friendships.