1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Graph Theory Proof

  1. Sep 19, 2011 #1
    Prove that if G is a simple graph with at least two vertices, then G has two or more vertices of the same degree.

    Assume its true for the base case 2 vertices with no edges or 2 vertices with one edge. Then either the degree is of both is 0 or the degree of both is 1. Therefore both vertices have the same degree.

    Now assume true for K vertices. WTS True for K+1 vertices.

    Since its true that K vertices have at least one pair of vertices of the same degree it follows immediately that K+1 vertices have at least one pair of vertices of the same degree.

    I was also thinking about doing this by contradiction and showing that if all the vertices are different degrees then there must be a loop but I was not sure how to say that.
  2. jcsd
  3. Sep 19, 2011 #2
    Why? Let's say v and w are the two verticies in your K-vertex graph that have the same degree. So you add the (K+1)th vertex, say x. What if there is an edge from x to v but not x to w? Then w and v no longer have the same degree, are they?

    OK, you are on the right track, here. Do you know what the pigeon-hole-principle is? So, if a simple graph G has n-verticies, then what are the options for the degree of a vertex in G?
  4. Sep 19, 2011 #3
    yep I guess you right, it would be easier if there were numbers to see that.

    Yeah I know the pigeon hole principle. Wouldn't the degree have to be at most n-1
  5. Sep 19, 2011 #4
    Exactly, each vertex can have degree 1, degree 2, ..., or degree n-1. Now, there are n verticies in the graph. Do you see what I see?
  6. Sep 19, 2011 #5
    I dont think so, we have n vertices and at most n-1 edges at any vertex, not sure how that would ensure that two of them are the same, wouldnt we need more edges than vertexes to ensure a loop or multiple edges?
    Last edited: Sep 19, 2011
  7. Sep 20, 2011 #6
    OK, so you want to show that two verticies have the same degree, not the same edge set. So, any vertex's degree has only n-1 possibilities but there are a total of n verticies. Now, what if no two verticies have the same degree? Do you see a contradiction?
  8. Sep 20, 2011 #7
    This can be shown using the pigeon hole principle.
  9. Sep 21, 2011 #8
    How can you use the pigeon hole principle? You have n different vertices and you n-1 edges or 0 edges so wouldn't you have n different possibilities for the number of edges?
  10. Sep 21, 2011 #9
    Assume that the graph has n verticies. 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 other vertices, thus ... .
  11. Sep 21, 2011 #10
    the vertex is connected to all of the vertices, but how does that ensure that there are at least two of the same degree? Wouldnt that only tell use something about that one vertex?

    Wait I think I got it is it because if there are n vertices and if one of them have n -1 edges then none of them have 0. So if there are n-1 vertices left but we can only choose 1 to n-2 edges with means we have 1 more vertex than the number of edges so there has to be a repeat.

    Is that right?
    Last edited: Sep 21, 2011
  12. Sep 22, 2011 #11
    It is correct. However, you could simplify it.
  13. Sep 22, 2011 #12
    How would you simplify it. Its two sentences long.
  14. Sep 22, 2011 #13
    The two most important things to remember are: (1) a proof is a logical argument, and must be clearly structured as such; and (2) your proof should be easily readable to any person with as much mathematical background as you.
  15. Sep 22, 2011 #14
    He said "simplify" not "shorten". You probably can't shorten it too much, but you can simplify it.
  16. Sep 22, 2011 #15
    I have never been very good at proofs other math I am fine with. Anyways, here it goes

    Assume that the graph G is simple and has n vertices and one of the vertices has n-1 edges. Then any of the other vertices can not have 0 edges because our first vertices is connected to all others. So we have n-1 vertices remaining and at most n-2 edges to choose from. By the pigeon hole principle this means that at least 2 vertices share a vertex degree because if we have 1 more vertex then edges to choose available.

    Is that simpler to understand... sadly it is not shorter.
  17. Sep 22, 2011 #16
    I think it is much simpler to understand.

    Well done.
  18. Sep 22, 2011 #17
    Thank you for you help.
  19. Sep 22, 2011 #18

    I don't think this is better. First of all, you start of by saying "assume...one of the verticies has n-1 edges." Then, if I understand, you make the (correct, given the assumption) argument that since each vertex is connected to the first vertex, then all of the other verticies have degree bigger than 0, from which you correctly apply PHP to the other n-1 verticies.

    Why do you start off assuming that one vertex has degree n-1? At best, your proof (as stated) only proves the case where one vertex has degree n-1. Unless you are going to do several cases (which is unnecessary, and you didn't do, anyway) you cannot make ANY assumptions about the graph that are not given to you in the statement. You know that G is simple, and that's it. So you know there are no loops, no double edges and no vertex has degree 0. Go from there, don't assume anything else.

    The proof should start something like this:

    "Let G be a simple graph on n verticies. Each vertex's degree can be as small as 1 or as large as n-1." Then go on from there.
  20. Sep 22, 2011 #19
    where can you go from there if you dont know what you have to start with. You have a bunch of nothing to work with? Would you say wlog assume a vertex has n-1 edges
    Last edited: Sep 22, 2011
  21. Sep 23, 2011 #20
    No, you do not say anything about a vertex having degree n-1 (or anything for that matter). I sort of see what you mean, but you can skip this step. You go from assuming there is a vertex of degree n-1 to saying exactly what you should say about the other n-1 verticies. In other words, the proof should go something like this:

    Let G be a simple graph on n verticies. Each vertex's degree can be as small as 1 or as large as n-1 for a total of n-1 options. Given that there are n verticies and n > n-1, by the PHP at least two verticies have the same degree.
  22. Sep 23, 2011 #21
    but couldn't the vertex degree be as small as 0?
  23. Sep 24, 2011 #22
    Yes it could; the proof I gave is not 100% complete. You'll need to add one line to the beginning, along the lines of "Let G be a connected graph on n verticies" (you will have to briefly mention the case where no verticies in G are connected, but this is easy, they all have degree 0.)
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook