• Support PF! Buy your school textbooks, materials and every day products Here!

Graph Theory Closed Trail

  • #1
123
0

Homework Statement



All vertices in a closed trail have even degree.

Homework Equations





The Attempt at a Solution



Intuitively, I know this statement is true, but I can't seem to see a clear way to show it. I know that a closed trail is a path that connects vertices, so one would follow an edge through a vertex to another edge, thus indicating that, on this particular path, this particular vertex has degree two. Clearly, a non-closed trail has endpoints which must have odd degree because they reach a stopping point on the trail, with a vertex incident to only one edge. Will you please help me put these facts into a coherent proof? Thank you.
 

Answers and Replies

  • #2
verty
Homework Helper
2,164
198
Hint: how could you make a closed trail shorter? Also, be sure you know exactly what a closed trail is.
 
  • #3
123
0
We could make a closed trail shorter by deleting a vertex. If we delete a vertex, the edges incident to that vertex are also deleted, so the trail would be shorter. But this action wouldn't necessarily affect the degree of vertices, would it?
 

Related Threads on Graph Theory Closed Trail

  • Last Post
Replies
11
Views
2K
Replies
2
Views
3K
Replies
4
Views
8K
Replies
1
Views
3K
Replies
13
Views
1K
Replies
1
Views
5K
Replies
7
Views
4K
  • Last Post
Replies
3
Views
1K
  • Last Post
Replies
4
Views
2K
  • Last Post
Replies
8
Views
1K
Top