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!

Graph theory trail proof

  1. Aug 29, 2013 #1
    1. The problem statement, all variables and given/known data
    Use ordinary induction on k or on the number of edges (one by one) to prove that a connected graph with 2k odd vertices composes into k trails if k > 0. Does this remain true without the connectedness hypothesis?


    2. Relevant equations



    3. The attempt at a solution
    If k = 1, the resulting graph is [tex]K_2[/tex], the complete graph on two vertices, both of which have odd degree. If we add an edge connecting these 2 vertices, we obtain an Eulerian circuit. Removing one edge reduces the graph to exactly 1 trail. Assume this proposition holds for k >= 1. I need to show that it holds for [tex]k + 1[/tex], i.e., [tex]2(k + 1)[/tex] odd vertices. Let G be a graph with [tex]2(k+1)[/tex] odd vertices. Label these vertices as [tex]u_1, u_2, ..., u_2k+2[/tex].

    And that's where I get stuck... I know that since G is connected, it contains trails, but I am not sure how to work this back to k trails...
    (Sorry about the latex; I can't remember how to make it not break to a new line).
     
  2. jcsd
  3. Aug 29, 2013 #2

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    Is it possible for a connected component to have an odd number of odd-valent vertices?
     
  4. Aug 30, 2013 #3
    No, a connected component cannot have an odd number of odd-valent vertices. Then could we say that since G cannot have an odd number of odd-valent vertices, there must be some (at least one) even-valent vertices which would indicate some (at least one) trails?
     
  5. Aug 30, 2013 #4

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    Right, so how does the 2k total decompose across the components? What can you say about decomposition into trails in each component?
     
  6. Aug 30, 2013 #5
    A trail contributes even degree to every vertex, except that non-closed trails contribute odd degree to their endpoints. Thus a single trail can have, at most, two vertices of odd degree, so the composition of G contains 2k odd vertices, divided by 2 vertices per trail = k trails. That should do it, right? Thank you very much.
     
  7. Aug 30, 2013 #6

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    That's not what I had in mind. You know that each component of G must have an even number of odd-valent vertices. Where that number > 0, the component decomposes into half that many trails. In that way, you decompose a disconnected graph with 2k odd-valent vertices into k trails provided... what?
     
  8. Aug 31, 2013 #7
    You are losing me here somewhat... I see that each trail has odd-valent vertices at its endpoints, so there would be two odd-valent vertices per trail. Then a graph with 2k odd-valent vertices would decompose into k trails provided the graph was Eulerian?
     
  9. Aug 31, 2013 #8

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    In the OP, you say you know that if a graph is connected and has 2k > 0 odd-valent vertices then it decomposes into k trails. Suppose more generally that a graph has n connected components. We've established that each must have an even number 2ki of odd-valent vertices, Ʃki = k. If the ith component decomposes into ki trails then we're home, right? How might that not be so? What condition are we missing on ki?
     
  10. Aug 31, 2013 #9
    I think the ith component must have odd vertices; otherwise we have a circuit, not a trail.
     
  11. Aug 31, 2013 #10

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    I'm not sure whether a trail is defined to have distinct endpoints. Maybe a circuit is just a special case of a trail? But even if a circuit is counted as a trail, you will still not be able to decompose the entire graph into k trails. Do you see why?
     
  12. Aug 31, 2013 #11
    The ith component would need odd vertices. Without that condition the graph could not be composed into k trails. Is that what you mean?
     
  13. Sep 2, 2013 #12

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    Yes. E.g. Consider a graph consisting of two connected components, K2 and K3. It satisfies the criteria in the OP (k=1), but does not consist of a single trail.
     
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: Graph theory trail proof
  1. Graph Theory Proof (Replies: 21)

  2. Graph Theory Proof (Replies: 3)

Loading...