Results 1 to 2 of 2

Math Help - Graph theory proof

  1. #1
    Junior Member
    Joined
    Mar 2009
    Posts
    30

    Graph theory proof

    Use graph theory to prove this statement:

    a party of n people, n>=2, at least two people will have the same number of friends. Assume the relationship is symmetric or irreflexive.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Newbie
    Joined
    Apr 2009
    Posts
    23
    Hi!

    Let d_i be the number of friends of vertex i (in the friendship graph,
    where vertices = party guests, edges = mutual friendship, no loops).
    Then
    <br />
0 \le d_i \le n-1<br />
    for all i.
    Assume that no two vertices have the same degree, i.e.
    <br />
d_i \neq d_j \; \mbox{for all} \;  i \neq j<br />
    That means that for every possible degree there is exactly
    one vertex with that degree. I.e., we may relabel the vertices
    with the integers 0,1,..,n-1
    so that after relabeling we have d_i = i \; (i=0,..,n-1)

    But this graph does not exist!
    Why?
    Well, vertex n-1 is adjacent to all n-1 other vertices,
    contradicting the fact that vertex 0 is not adjacent to anyone else.

    qed

    Best,

    ZD
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Graph Theory Proof
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: April 4th 2011, 12:16 AM
  2. graph theory proof
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: May 7th 2010, 11:59 AM
  3. Graph theory proof
    Posted in the Advanced Math Topics Forum
    Replies: 0
    Last Post: May 6th 2010, 05:27 AM
  4. graph theory proof
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: April 5th 2010, 08:34 AM
  5. Graph theory: proof
    Posted in the Discrete Math Forum
    Replies: 7
    Last Post: October 29th 2009, 12:00 PM

Search Tags


/mathhelpforum @mathhelpforum