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

Question on Graph theory

  1. Mar 2, 2005 #1
    I'm not sure where to post this, but anyway here is the question:

    Given a graph G(p,q) is a tree where p is the number of vertices and q is the number of edges.

    Since given graph is a tree, number of edges q=p-1.

    How do you prove that every non-trivial tree has atleast two vertices with degree less than 2?

    P.S.: A tree is a connected acyclic graph.
     
  2. jcsd
  3. Mar 2, 2005 #2

    shmoe

    User Avatar
    Science Advisor
    Homework Helper

    Sum up the degrees of the vertices in two ways, once as a sum over the vertices and once as a sum over the edges. Assume you don't have two vertices with degree one, use this assumption to get a lower bound for the sum of the degrees and you'll find a contradiction.
     
  4. Mar 2, 2005 #3
    Thanks for replying.

    Here is my proof:
    Graph G(p,q) is a tree. Hence q=p-1.
    Let us assume that the tree does not have any vertices with degree 1.
    Let [tex]d_i[/tex] represent degree of any vertex i ranging from 1 to p.

    We know [tex]\sum d_i = 2q[/tex]
    [tex]\sum d_i = 2p-2 [/tex]

    How do you get a lower bound on this and get a contradiction?
     
  5. Mar 3, 2005 #4
    Can someone help?
     
  6. Mar 5, 2005 #5

    shmoe

    User Avatar
    Science Advisor
    Homework Helper

    Well if you assumed you had no vertices of degree 1, then each [tex]d_i[/tex] must be greater than or equal to what number? What does this say about [tex]\sum d_i[/tex], keeping in mind that [tex]p[/tex] is the number of vertices?

    Can we modify this slightly to rule out the possiblity of only one vertex of degree 1? What about 2 vertices of degree 1, is this possible?
     
    Last edited: Mar 5, 2005
  7. Mar 5, 2005 #6
    OK,based on the assumption--each [tex]d_i[/tex] is greater than or equal to 2.

    How do you now prove there are atleast 2 verices of degree 1?
     
  8. Mar 7, 2005 #7

    shmoe

    User Avatar
    Science Advisor
    Homework Helper

    You're adding up p things, each of which is at least 2, so [tex]\sum d_i \geq ???[/tex]
     
  9. Mar 9, 2005 #8
    Ok, so [tex]\sum d_i \geq 2p[/tex]....which is a contradiction.
    Hence there are atleast 2 vertices of degree 1.

    Thank you.
     
  10. Mar 9, 2005 #9

    shmoe

    User Avatar
    Science Advisor
    Homework Helper

    Hang on, this lower bound of 2p came from the assumption that we had no vertices of degree 1, so this contradiction only tells you that you have at least one vertex of degree 1. The point of this cse was to give you a (slightly) simpler version to try first.

    What inequality do you get if you assume you have only one vertex of degree 1? You should get a similar contradiction.
     
  11. Mar 10, 2005 #10
    I'm sorry, I cannot arrive at any contradiction :cry:
    can you help?
     
  12. Mar 10, 2005 #11

    shmoe

    User Avatar
    Science Advisor
    Homework Helper

    Let's make the indicies explicit. You know:

    [tex]\sum_{i=1}^{p}d_i=2p-2[/tex]

    Now suppose you have 1 vertex with degree 1, the rest two or more. Without loss of generality assume [tex]d_p=1[/tex] and [tex]d_i\geq 2[/tex] for all 1<=i<p. Using this, what is a lower bound for the sum?
     
  13. Mar 11, 2005 #12
    The lower bound is: [tex]\sum d_i \geq 2p+1[/tex]
    Right? This also a contradiction. Hence there has to be atleast 2 verices of degree 1.

    Hope I got it right this time.
     
  14. Mar 11, 2005 #13

    shmoe

    User Avatar
    Science Advisor
    Homework Helper

    Why the +1?

    break the sum up:

    [tex]\sum_{i=1}^{p}d_i=d_p+\sum_{i=1}^{p-1}d_i[/tex]

    and use my assumption above that the pth vertex was the only one with degree 1, the rest (all p-1 of them) have degree 2 or more..
     
  15. Mar 12, 2005 #14
    [tex]\sum_{i=1}^{p}d_i=d_p+\sum_{i=1}^{p-1}d_i[/tex]

    [tex]\sum_{i=1}^{p}d_i=2p-2[/tex]

    [tex]d_p=1[/tex]

    [tex]\sum_{i=1}^{p-1}d_i\geq 2(p-1)[/tex]
    --->right?
     
  16. Mar 12, 2005 #15

    shmoe

    User Avatar
    Science Advisor
    Homework Helper

    Good, now combine everything.
     
  17. Mar 12, 2005 #16

    mathwonk

    User Avatar
    Science Advisor
    Homework Helper
    2015 Award

    use induction on the number of edges. It is true if there is only one edge.

    Now just collapse any edge, collapsing vertex a to vertex b. The result is true for the new graph by induction. If collapsing the edge changed the degree of b from 2 to one, it is obvious that either b or a also had degree one originally.


    done.

    moral: induction is a ridiculously powerful tool.
     
    Last edited: Mar 12, 2005
  18. Mar 13, 2005 #17
    [tex]\sum_{i=1}^{p}d_i=d_p+\sum_{i=1}^{p-1}d_i[/tex]
    Hence, [tex] 2p-2 = 1 + [2(p-1)]_{min}[/tex]

    You get an absurd equation. Hence a contradiction.
     
  19. Mar 13, 2005 #18

    mathwonk

    User Avatar
    Science Advisor
    Homework Helper
    2015 Award

    what do you think of the inductive argument? doesn't it seem easier?
     
  20. Mar 13, 2005 #19
    No, I find the inductive aurgument pretty difficult to understand. Sorry :frown:
     
  21. Mar 13, 2005 #20

    mathwonk

    User Avatar
    Science Advisor
    Homework Helper
    2015 Award

    let me try to explain it more clearly:

    we wish to show that a non trivial finite tree has at least two vertices of degree one, i.e. from which there emanate only one edge. We will argue by induction on the number n of edges.

    By definition, a non trivial tree has at least one edge. So we begin the induction with the case n=1. Then it is clear that both vertices have exactly one edge and we are done.

    Now assume the result for all graphs with n-1 edges, and let us consider a graph G with n ≥ 2 edges.

    Choose any edge e at all, with endpoints a and b, and collapse e to a point.

    This produces a new graph G' with n-1 edges. The two endpoints a and b of e have been combined together into one new vertex called c.

    Now let's compute the degree of c. I claim deg(c) = deg(a) + deg(b) -2.

    I.e. all edges, except for e, that used to end at either a or b now end at c, so we must add them. (Since G was a tree, only one edge, namely e, ended at both a and b, so a and b had no edges in common except for e.) Since the missing edge e counted as one for both deg(a) and deg(b), we must subtract it twice have our formula. i.e. deg(c) = deg(a)-1 + deg(b)-1.

    Now deg(c) cannot be zero, since that would mean that G had only the one edge e.

    Consequently, deg(c) ≥ 1, and if deg(c) =1, then either deg(a) or deg(b)=1.

    All other vertices of G' have the same degree they had in G, since they fail to meet e.

    Now by the inductive hypothesis, there are two vertices say x,y, of G' of degree one. If neither of these is c, we are done, since our collapsing process did not affect them, so the same two vertices on G also had degree one.

    If it happens that say x = c, then deg(c) =1, so either a or b had degree 1 in G, say deg(a) = 1. Then in G we had at least two vertices of degree one, namely a and y.

    Does this seem clearer?
     
    Last edited: Mar 13, 2005
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Question on Graph theory
  1. Question on Graph (Replies: 1)

  2. Graph theory (Replies: 1)

Loading...