Results 1 to 3 of 3

Math Help - a graph problem

  1. #1
    Newbie
    Joined
    Jan 2009
    Posts
    7

    a graph problem

    1- Show that in a simple graph G having at least two vertices, there must be two distinct vertices having the same degree.

    2- Use the result of 1 to show that in any group of at least two people there must be two people who know the same number of people in the group.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,639
    Thanks
    1592
    Awards
    1
    I hope that this does not disappoint, but I am not giving you more that hints.
    In a simple graph of order n, the maximum vertex degree is n-1.
    Thus any degree sequence if distinct values must be: 0,1,2, \cdots ,n - 1.
    But, if the graph has a vertex of degree zero, we can drop it.
    Recall that the sum of the degrees is twice the number of edges.

    Try to find a contradiction in all that.

    2) Follows trivially from #1.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Jan 2009
    Posts
    7
    thanks for the help, i tried and thats what i got, is that correct?
    Attached Thumbnails Attached Thumbnails a graph problem-ab12.jpg  
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. ti-83 sin graph problem
    Posted in the Calculators Forum
    Replies: 5
    Last Post: December 29th 2011, 04:43 AM
  2. graph problem..
    Posted in the Math Topics Forum
    Replies: 2
    Last Post: September 12th 2009, 08:13 AM
  3. Please help ! Graph problem
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: October 18th 2008, 07:11 AM
  4. Graph Problem
    Posted in the Algebra Forum
    Replies: 3
    Last Post: July 4th 2007, 11:47 AM
  5. A Graph Problem :?
    Posted in the Pre-Calculus Forum
    Replies: 5
    Last Post: May 15th 2007, 11:23 AM

Search Tags


/mathhelpforum @mathhelpforum