Proving the theorem of graph theory

Question

I want to know the proof of the condition of a Euler walk or tour in a directed graph.

I googled a lot about it from MIT courseware to some other YouTube channels but I couldn't find any proof for the above condition. Please help

Thanks in advance.

Answer 1

Any introductory graph theory book should present a proof. Diestel's book is available online here, and there is a proof in Section 1.8.

Answer 2

In any kind of circuit all edges have even degree (since every time you go into that vertex you must also go out). In any kind of trail there are $0$ or $2$ vertices with odd degree.The trails with $0$ odd vertices are all cycles, since trails with ends in different vertices contain $1$ vertex from which we departed without ever going in and another vertex which we arrived at without leaving.

So clearly a necessary condition for a connected graph $G$ to have an Eulerian circuit is that all of the vertices of $G$ have even degree, and a necessary condition for $G$ to have an Eulerian trail is that $G$ has $0$ or $2$ vertices of odd degree.

We shall prove it is sufficient by induction on the number of edges. the base case of the triangle is clearly true.Our inductive Hypothesis is that if $G$ is a connected graph with $k$ or less edges which has only vertices of even degree then it contains an Eulerian circuit.

Now suppose $H$ is a connected graph which has only even vertices. The $H$ contains a cycle $C$. After we remove that cycle $C$ we are left with a collection of connected components, each of which also has only vertices of even degree, and by the inductive hypothesis its own eulerian cycle. We now build an eulerian cycle for $H$. pick a vertex on $C$, traverse along $C$ until we reach a vertex belonging to one of the connected components. Then traverse along its eulerian circuit back to the same vertex of $C$, then transverse along $C$ until you get to the next connected component, and traverse that component's eulerian cycle, and so on untill you trasverse all of $C$, at that point you will have traversed each edge exactly once and will have returned to the starting point.

Since an eulerian trail is an Eulerian circuit, a graph with all its degrees even also contains an eulerian trail. Now let $H$ be a graph with $2$ vertices of odd degree $v_1$ and $v_2$ if the edge between them is in $H$ remove it, we now have an eulerian circuit on this new graph. So if we use that circuit to go from $v_1$ back to $v_1$ and then go from $v_1$ to $v_2$ we get an eulerian trail on $H$. If the edge between $v_1$ and $v_2$ does not exist then add it. There now exists an eulerian circuit from $v_1$ to $v_1$ removing that edge again gives us an eulerian tour.