JT's

An Euler trail is a walk that uses every edge of a graph exactly once.

An Euler circuit is a circuit that uses every edge of a graph exactly once.

A Euler trail with same endpoints is a Euler circuit.

Here are some examples:

Letbe a finite connected graph and denote the number of vertices that have odd degrees.

Prove that G has a Euler trail if and only if .

First, by the Handshake Theorem, we can narrow down our range of :

An arbitrary can have . We will now try to show that some subset of , those that have Euler trails,  have .

Proof() : We know such that includes all edges of exactly once.

Case 1 : has endpoints 

             It has middle vertices (vertices that are not endpoints).

      By definition of a middle vertex, the trail does not end at , i.e. if it enters it has to leave it through 

      an edge.

      Therefore, we can easily see that has an even degree.

             Now consider . They may appear in multiple times but but each time they do so, they have a pair                 of edges entering and leaving them, EXCEPT when they are endpoints. In this case there's only 

             one edge leaving , the start of , and only one entering .

             Hence have one more edge entering and one more edge leaving, respectively.

              , so the claim holds in this direction.

Case 2 : has endpoints , so we have an Eulerian cycle that starts and ends at .

             For every vertex other than , edges in leave it and every time they enter .

             has an even degree.

             Consider  . When it appears in not as the start/end point of the cycle, same things happens to it as   

              .

             As the 종점 of the cycle, an edge leaves in the beginning and enters it at the end. has an even degree 

             as well.

             , so the claim holds in this direction.

Contrapositives rule out the possibility of Euler trails in graphs with more than 2 odd degrees.

Proof() : See Proof - Euler Trail Theorem (2)

Generalize to a trail : 

Consider a trail in any graph. If we see the trail as a subgraph on its own, this is an Euler trail. Then we can apply the Euler Trail Theorem to learn something about the degree of vertices in the trail.