1. Limited time only! Sign up for a free 30min personal 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!

Homework Help: Graph Theory Closed Trail

  1. Sep 5, 2013 #1
    1. The problem statement, all variables and given/known data

    All vertices in a closed trail have even degree.

    2. Relevant equations

    3. 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.
  2. jcsd
  3. Sep 5, 2013 #2


    User Avatar
    Homework Helper

    Hint: how could you make a closed trail shorter? Also, be sure you know exactly what a closed trail is.
  4. Sep 5, 2013 #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?
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted