Proving the Even Degree Property of Vertices in Closed Trails

In summary, the conversation discusses the concept of closed trails and their degree. It is stated that all vertices in a closed trail have even degree, and the attempt at a solution includes an explanation of how this is intuitive but difficult to prove. The hint suggests making the closed trail shorter and considering the definition of a closed trail. The conversation ends with a suggestion to delete a vertex to make the closed trail shorter, but it is uncertain if this would affect the degree of the vertices.
  • #1
tarheelborn
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.
 
Physics news on Phys.org
  • #2
Hint: how could you make a closed trail shorter? Also, be sure you know exactly what a closed trail is.
 
  • #3
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?
 

1. What is a closed trail in graph theory?

A closed trail in graph theory is a path in a graph that starts and ends at the same vertex, and does not repeat any edges or vertices. It can also be referred to as a circuit or a closed walk.

2. How is a closed trail different from a closed path?

A closed trail is a specific type of closed path that allows for repeating vertices, while a closed path does not allow for any repeating edges or vertices.

3. What is the importance of closed trails in graph theory?

Closed trails are important in graph theory because they help us understand the connectivity and structure of a graph. They can also be used to solve practical problems, such as finding the shortest route between two points in a transportation network.

4. Can a closed trail exist in a directed graph?

Yes, a closed trail can exist in a directed graph. In this case, the trail must start and end at the same vertex, and the edges must be traversed in the correct direction to form a closed loop.

5. How is a closed trail different from a closed cycle?

A closed trail is a path that starts and ends at the same vertex, while a closed cycle is a path that starts and ends at the same vertex and also does not repeat any edges or vertices. In other words, a closed trail is a type of closed cycle, but a closed cycle is not always a closed trail.

Similar threads

  • Calculus and Beyond Homework Help
Replies
1
Views
1K
  • Calculus and Beyond Homework Help
Replies
11
Views
4K
  • Calculus and Beyond Homework Help
Replies
3
Views
2K
  • Calculus and Beyond Homework Help
Replies
2
Views
4K
  • Calculus and Beyond Homework Help
Replies
2
Views
979
  • Calculus and Beyond Homework Help
Replies
5
Views
12K
  • Calculus and Beyond Homework Help
Replies
5
Views
3K
  • Calculus and Beyond Homework Help
Replies
3
Views
2K
Replies
34
Views
4K
  • Calculus and Beyond Homework Help
Replies
3
Views
1K
Back
Top