# Proving that a Euler Circuit has a even degree for every vertex

Theorem: Given a graph G has a Euler Circuit, then every vertex of G has a even degree

Proof: We must show that for an arbitrary vertex v of G, v has a positive even degree.

What does it mean by every even degree? When I think of an even degree I think of polynomial functions.

What I am trying to prove?

• It means the number of edges incident with the vertex(degree) is even
– hbm
Feb 11, 2014 at 0:07
• @hbm Look at the Euler circuit I just put. v4 has 5 edges... Please explain Feb 11, 2014 at 0:16
• Typically, a "graph" is assumed to refer to a simple, undirected graph, and accordingly theorems are typically stated for such graphs (unless otherwise specified). Simple graphs are graphs which have no multiple edges between vertices and no edges from a vertex to itself (called a "loop"). Directed graphs (called "digraphs") have an orientation to their edges while undirected graphs do not. Your graph is neither simple, nor undirected, so you wouldn't normally expect a theorem given for a normal graph to hold.
– EuYu
Feb 11, 2014 at 0:38
• In this case however, there is a corresponding theorem for digraphs which says that a digraph (possibly with multiple edges and loops) has an Eulerian circuit if and only if every vertex has indegree equal to outdegree and are part of the same strongly connected component. That theorem holds for your graph.
– EuYu
Feb 11, 2014 at 0:40
• Well, loops count twice.
– hbm
Feb 11, 2014 at 0:55

An Eulerian circuit is a traversal of all the edges of a simple graph once and only once, staring at one vertex and ending at the same vertex. You can repeat vertices as many times as you want, but you can never repeat an edge once it is traversed.

The degree of a vertex is the number of edges incident with that vertex.

So let $G$ be a graph that has an Eulerian circuit. Every time we arrive at a vertex during our traversal of $G$, we enter via one edge and exit via another. Thus there must be an even number of edges at every vertex. Therefore, every vertex of $G$ has even degree.

Proof. For the first implication, take $$X = (V, E)$$ as the Eulerian graph with a closed Eulerian trail $$T \equiv [v_0 v_1 \cdots v_{k−1} v_k]$$ with $$v_k = v_0$$.

Due to the nature of the trail, for each $$v \in 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 $$2$$ to the 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, assume that each vertex of $$X$$ has an 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′$$ 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$$, construct the desired closed Eulerian trail as follows :

Start with a vertex, say $$v_0$$ of $$C$$.

If there is a component of $$X′$$ having $$v_0$$ as a vertex, then traverse this component and come back to $$v_0$$. This is possible as each component is Eulerian.

Now, proceed along the edges of $$C$$ until we get another component of $$X′$$, say at $$v_1$$. Traverse the new component of $$X′$$ starting with $$v_1$$ and again come back to $$v_1$$.

This process terminates as and when we return to the vertex $$v_0$$ of $$C$$.

Thus, we have obtained the required closed Eulerian trail. $$\blacksquare$$

Proof: If G is Eulerian then there is an Euler circuit, P, in G. Every time a vertex is listed, that accounts for two edges adjacent to that vertex, the one before it in the list and the one after it in the list. This circuit uses every edge exactly once. So every edge is accounted for and there are no repeats. Thus every degree must be even. Suppose every degree is even. We will show that there is an Euler circuit by induction on the number of edges in the graph. The base case is for a graph G with two vertices with two edges between them. This graph is obviously Eulerian. Now suppose we have a graph G on m > 2 edges. We start at an arbitrary vertex v and follow edges, arbitrarily selecting one after another until we return to v. Call this trail W. We know that we will return to v eventually because every time we encounter a vertex other than v we are listing one edge adjacent to it. There are an even number of edges adjacent to every vertex, so there will always be a suitable unused edge to list next. So this process will always lead us back to v. Let E be the edges of W. The graph G ¡ E has components C1;C2; : : : ;Ck. These each satisfy the induction hypothesis: connected, less than m edges, and every degree is even. We know that every degree is even in G ¡ E, because when we removed W, we removed an even number of edges from those vertices listed in the circuit. By induction, each circuit has an Eulerian circuit, call them E1;E2; : : : ;Ek. Since G is connected, there is a vertex ai in each component Ci on both W and Ei. Without loss of generality, assume that as we follow W, the vertices a1; a2; : : : ; ak are encountered in that order. We describe an Euler circuit in G by starting at v follow W until reaching a1, follow the entire E1 ending back at a1, follow W until reaching a2, follow the entire E2, ending back at a2 and so on. End by following W until reaching ak, follow the entire Ek, ending back at ak, then ¯nish o® W, ending at v.