Graph theory trail proof

  • #1
123
0

Homework Statement


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?


Homework Equations





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).
 

Answers and Replies

  • #2
haruspex
Science Advisor
Homework Helper
Insights Author
Gold Member
34,255
5,830
Is it possible for a connected component to have an odd number of odd-valent vertices?
 
  • Like
Likes 1 person
  • #3
123
0
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?
 
  • #4
haruspex
Science Advisor
Homework Helper
Insights Author
Gold Member
34,255
5,830
No, a connected component cannot have an odd number of odd-valent vertices.
Right, so how does the 2k total decompose across the components? What can you say about decomposition into trails in each component?
 
  • #5
123
0
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.
 
  • #6
haruspex
Science Advisor
Homework Helper
Insights Author
Gold Member
34,255
5,830
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.
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?
 
  • #7
123
0
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?
 
  • #8
haruspex
Science Advisor
Homework Helper
Insights Author
Gold Member
34,255
5,830
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?
 
  • #9
123
0
I think the ith component must have odd vertices; otherwise we have a circuit, not a trail.
 
  • #10
haruspex
Science Advisor
Homework Helper
Insights Author
Gold Member
34,255
5,830
I think the ith component must have odd vertices; otherwise we have a circuit, not a trail.
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?
 
  • #11
123
0
The ith component would need odd vertices. Without that condition the graph could not be composed into k trails. Is that what you mean?
 
  • #12
haruspex
Science Advisor
Homework Helper
Insights Author
Gold Member
34,255
5,830
The ith component would need odd vertices. Without that condition the graph could not be composed into k trails. Is that what you mean?
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.
 
  • Like
Likes 1 person

Related Threads on Graph theory trail proof

  • Last Post
Replies
2
Views
835
Top