Let X = (V, E) be an Eulerian graph with a closed Eulerian trail T ≡ [v0v1 . . . vk−1vk = v0].
By the very nature of the trail, for each v ∈ V, the trail T enters v through an edge and departs v from another edge of X. Thus, at each stage, the process of coming in and going out, contributes two to degree of v.
In addition, the trail T passes through each edge of X exactly once and hence each vertex must be of even degree.
Conversely, let us assume that each vertex of X has even degree. We need to show that X is Eulerian. We prove the result by induction on the number of edges of X.
As each vertex has even degree and X is connected, hence X contains a circuit, say C. If C contains every edge of X, then C gives rise to a closed Eulerian trail and we are done. So, let us assume that C is a proper subset of E.
Now, consider the graph X′ that obtained from X by removing all the edges in C. Then, X′ may be a disconnected graph but each vertex of X′ still has even degree.
Hence, we can use induction to each component to X′ to get a closed Eulerian trail for each component of X′.
As each component of X′ has at least one vertex in common with C, we use the following method to construct the required closed Eulerian trail: start with a vertex, say v0 of C.
If there is a component of X′ having v0 as a vertex, then traverse this component and come back to v0. This is possible as each component is Eulerian.
Now, proceed along the edges of C until we get another component of X′, say at v1. Traverse the new component of X′ starting with v1 and again come back to v1.
This process will end as soon as we return to the vertex v0 of C.
Thus, we have obtained the required closed Eulerian trail.