Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Simple graph with at least two vertices

  1. Feb 28, 2007 #1

    please help by exaplaining this question in steps thank much

    Show that in a simple graph with at least two vertices there must be
    two vertices that have the same degree. use the Pigeonhole principle.
  2. jcsd
  3. Feb 28, 2007 #2


    User Avatar
    Staff Emeritus
    Science Advisor

    You must show your work before we can help you. Have you thought about the question? Have you tried following the hint?
  4. Mar 1, 2007 #3


    User Avatar
    Science Advisor

    Have you at least drawn a picture? What happens if you try to draw a graph with exactly two vertices, each vertex having different degree?
  5. Mar 1, 2007 #4
    thanx for replyng i did draw a graph but i still can't understand the whole question
    i know that Each vertices is connected to either 0, 1, 2, ..., n−1 other vertices but i cannot get the whole idea

    please help
  6. Mar 1, 2007 #5
    so let's say you have n vertices. As you said, assume they all have different degree, then they must be,

    however, how can a vertex have zero degree while another vertex have n-1 degree (connecting to ALL other vertices)? contradiction.
  7. Mar 1, 2007 #6
    a more interesting question would be:

    let there be n people in a party. Alex is in the party, and he knows that all the other people make different number of handshakes, how many handshakes does Alex make?

    this classic handshake problem is closely related to this situation.
  8. Mar 1, 2007 #7
    please explain more in details
  9. Mar 4, 2007 #8
    okey can you tell me ur opinion on this thanx

    Assume that the graph has n vertices. Each of those vertices is connected to either 0, 1, 2, ..., n−1 other vertices. If any of the vertices is connected to n−1 vertices, then it is connected to all the others, so there cannot be a vertex connected to 0 others. Thus, it is impossible to have a graph with n vertices where one vertex has degree 0 and another has degree n−1. Thus the vertices can have at most n−1 different degrees, but since there are n vertices, at least two must have the same degree.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook