The following is an excerpt of the proof that if a connected graph has all vertices of even degree that is has an euler tour.

We must prove that every connected graph with all vertices of even degree is eulerian. We shall prove this by contradiction. Suppose there exists a connected graph with all vertices of even degree that is not eulerian. Among such graphs, let $G$ be one with the smallest number of edges. Let T be a longest trail in $G$. Since every vertex in $G$ has even degree and $T$ cannot be extended, $T$ must be a closed trail.

My question is regarding to this last statement. Why is it true that $T$ must be a closed trail?


If $T$ could be extended then $T$ would not be the longest trail in $G$.

  • $\begingroup$ how does this relate to it being closed. $\endgroup$ Feb 23 '17 at 1:22
  • 2
    $\begingroup$ If it were not closed, it would have endpoints. Since all vertices have even degree, from an endpoint there must be another edge that could be used to extend the trail. $\endgroup$ Feb 23 '17 at 1:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.