Results 1 to 3 of 3
Like Tree1Thanks
  • 1 Post By Plato

Thread: (Graph Theory) Minimum possible number of friendships

  1. #1
    Newbie
    Joined
    Sep 2018
    From
    Europe
    Posts
    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?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    22,078
    Thanks
    2981
    Awards
    1

    Re: (Graph Theory) Minimum possible number of friendships

    Quote Originally Posted by nkole View Post
    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.
    Thanks from SlipEternal
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor
    Joined
    Nov 2010
    Posts
    3,722
    Thanks
    1515

    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.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 5
    Last Post: Dec 16th 2015, 11:10 AM
  2. Graph Theory / Chromatic Number of a Complete Graph
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: Nov 15th 2011, 10:59 AM
  3. Minimum number of edges in a graph of order n
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: Oct 12th 2011, 04:27 PM
  4. Minimum number to remove from a complete graph
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: Oct 14th 2010, 04:11 PM
  5. graph theory, chromatic number relation
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: May 6th 2009, 04:05 AM

Search Tags


/mathhelpforum @mathhelpforum