Theorem 3.1 (Euler) A connected graph G is an Euler graph if and only if all vertices of G are of even degree.

Necessity Let G(V, E) be an Euler graph. Thus G contains an Euler line Z, which is a closed walk. Let this walk start and end at the vertex u ∈ V. Since each visit of Z to an intermediate vertex v of Z contributes two to the degree of v and since Z traverses each edge exactly once, d(v) is even for every such vertex. Each intermediate visit to u contributes two to the degree of u, and also the initial and final edges of Z contribute one each to the degree of u. So the degree d(u) of u is also even.

Second proof for sufficiency Assume that all vertices of G are of even degree. We construct a walk starting at an arbitrary vertex v and going through the edges of G such that no edge of G is traced more than once. The tracing is continued as far as possible. Since every vertex is of even degree, we exit from the vertex we enter and the tracing clearly cannot stop at any vertex but v. As v is also of even degree, we reach v when the tracing comes to an end. If this closed walk Z we just traced includes all the edges of G, then G is an Euler graph. If not, we remove from G all the edges in Z and obtain a subgraph Z 0 of G formed by the remaining edges. Since both G and Z have all their vertices of even degree, the degrees of the vertices of Z 0 are also even. Also, Z 0 touches Z at least at one vertex say u, because G is connected. Starting from u, we again construct a new walk in Z 0 . As all the vertices of Z 0 are of even degree, therefore this walk in Z 0 terminates at vertex u. This walk in Z 0combined with Z forms a new walk, which starts and ends at the vertex v and has more edges than Z. This process is repeated till we obtain a closed walk that traces all the edges of G.

What is the mathematical defination of "touches"? Can you provide a proof for this line


Touches here simply means that $Z_0$ and $Z$ have at least one vertex in common. Unfortunately, the quoted passage doesn’t define $Z_0$ quite right. Specifically, it says that $Z_0$ is what’s left when we remove from $G$ every edge that appears in the walk $Z$, and this may not be quite enough: we may need to remove some vertices as well.

Suppose that $v$ is a vertex that appears in $Z$. Removing from $G$ the edges that are in $Z$ may remove every edge of $G$ that is adjacent to $v$, leaving $v$ as a completely isolated vertex; in this case we also want to remove $v$ from $G$. If there is any edge adjacent to $v$ that is not on the path $Z$, then we keep $v$ as a vertex of $Z_0$.

Now saying that $Z_0$ and $Z$ have at least one vertex in common is just saying that $G$ has at least one vertex $v$ such that the walk $Z$ does not ‘use up’ all of the edges adjacent to $v$. Suppose that this is not the case. Then if $v$ is a vertex on $Z$, every edge adjacent to $v$ appears in the walk $Z$, and $v$ is not in $Z_0$. The vertices to which $v$ is connected by an edge are all in $Z$ and therefore not in $Z_0$. This means that $G$ has no edges between any vertex in $Z$ and any vertex in $Z_0$, which is impossible if $G$ is connected and $Z$ and $Z_0$ are both non-empty.


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.