1. Not finding help here? Sign up for a free 30min 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!

Combinatorics: Finite Graph

  1. Apr 23, 2015 #1
    1. The problem statement, all variables and given/known data

    Show that any finite graph contains two vertices lying on the same number of edges.

    2. Relevant equations

    None

    3. The attempt at a solution

    I am confused how my book proved this.

    Let G be a graph with n vertices ##v_1, ..., v_n.## Place ##v_i## in a pigeonhole labelled ##m## if it has exactly ##m## neighbours. The possible labels on the pigeonholes are ##0,1,2,..., n-1## so ##n## vertices are placed in ##n## pigeonholes. However, the pigeon-holes labelled ##0## and ##n-1## cannot both be occupied.

    Why can't they both not be occupied? And what exactly do they mean by occupied?
     
  2. jcsd
  3. Apr 23, 2015 #2

    ehild

    User Avatar
    Homework Helper
    Gold Member

    An occupied pigeon-hole labelled by k contains the vertices having k neighbours.
    If there are n vertices, and one of them has no neighbours, no other vertices are connected to it. What is the maximum number of edges from one vertex?
    In a graph of n vertices, the maximum number of the edges from a vertex is n-1. If there is a vertex with n-1 neighbours, it means every vertex is connected to that one. Is there any vertex without neighbours then?
     
    Last edited: Apr 24, 2015
  4. Apr 24, 2015 #3

    epenguin

    User Avatar
    Homework Helper
    Gold Member

    Never knew this nor occurred to me. Can you prove it by simple induction? I would like to see it done.

    Seems to me if you draw a graph the first step is one edge between two vertices, and thereafter you can never add an edge in such a way that the theorem is violated. ?
     
  5. Apr 24, 2015 #4

    ehild

    User Avatar
    Homework Helper
    Gold Member

    My post was answer to the question of the OP, about occupancy of the "pigeonholes", and was not connected to the solution of the problem itself. For me, it is not quite clear what the sentence
    means. Is it that there are at least two vertices with the same number of neighbours?
     
    Last edited: Apr 24, 2015
  6. Apr 24, 2015 #5

    epenguin

    User Avatar
    Homework Helper
    Gold Member

    That's what I thought it meant.
     
  7. Apr 24, 2015 #6

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    I've also seen the problem stated as "Show every finite graph has two vertices with equal degree". So I think that interpretation is correct.
     
  8. Apr 25, 2015 #7
    Can you elaborate on this, please? I have trouble understanding combinatorics without examples.

    I've noticed, when I am studying combinatorics, that I have to re-read the questions many times (at least 15 times lol) for me to understand it, is that normal? I don't have that problem with my other classes.
     
  9. Apr 25, 2015 #8

    ehild

    User Avatar
    Homework Helper
    Gold Member

    With the "pigeonhole" method, you have to arrange N vertices in N-1 holes.

    See picture. You have a connected graph, with N=5 vertices.

    graphneighbours.JPG

    B and C both have one neighbour each. D and E both have two neighbours. A has 4 neighbours. Maximum number of edges connected to a vertex is 4.

    If you add an isolated vertex, which is not connected to any other point, the graph consists of 6 vertices, but the maximum number of neighbours is still 4. The hole labelled by 5 is empty. So consider connected graphs only.
    graphnotconnect.JPG



    You have to put N vertices into N-1 holes. Is it possible with a single vertex in each hole?
    Combinatorics needs a special way of thinking, For me, it is difficult , too. :oldmad: Make drawings, it helps!
     
  10. Apr 25, 2015 #9

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    Frankly, the book's method is making an easy solution look hard.
    Suppose every vertex can have a different degree. What's the least degree a vertex can have? What's the greatest degree a vertex can have if there are n vertices? If the are n different degrees in the graph, what are they? Is such a graph possible? In particular, can that minimum degree and that maximum degree coexist in one graph?
     
  11. Apr 25, 2015 #10
    Thank you very much, that was very helpful!

    Thank you!
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Combinatorics: Finite Graph
  1. Combinatorics question (Replies: 2)

Loading...