I am looking at the proof that $G$ has an Euler tour iff in-degree($v$)=out-degree($v$), that I found at this site: www.cs.duke.edu/courses/fall09/cps230/hws/hw3/headsol.pdf (Problem 2)
A simple cycle is a path in a graph that starts and ends at the same vertex without passing through the same vertex more than once.
A complex cycle is a cycle that passes through the same vertex more than once. We can easily decompose a complex cycle to a set of simple cycles by breaking up the cycle at those points where the cycle passes through the same vertex more than once.
As the first part of our proof, we will prove that if $G$ has an Euler tour, in-degree($v$)=out-degree($v$) for each vertex $v \in V$.
We have already established that a complex cycle can be decomposed to a collection of simple cycles. However vertices on a simple cycle have in-degree($v$)=out-degree($v$)=1.
Since each vertex in a complex cycle, and therefore in an Euler tour, is part of one or more simple cycles it will have in-degree($v$)=out-degree($v$).
- Could you give me an example of a complex cycle that is decomposed to a set of simple cycles, where we can see that in-degree($v$)=out-degree($v$)?
The second part of our proof requires us to prove that if in-degree($v$)=out-degree($v$) for each vertex $v \in V$, $G$ has an Euler-tour.
Let $C$ be the complex cycle involving the most edges in $G$.
In order for $G$ not to be an Euler tour, there must be some vertices that $C$ passes through ( since the graph is connected ) but does not exhaust all edges. We have already established that the vertices of a complex cycle have the property that in-degree($v$)=out-degree($v$). Therefore $G'=G-C$ will also have that property. If a connected component in a graph has in-degree($v$)=out-degree($v$) then it contains at least one cycle $C'$. However this contradicts our initial hypothesis that $C$ is the cycle involving the most edges in $G$ since we would construct a larger cycle by starting at some common vertex of $C$ and $C'$, traversing all of $C$s edges and then $C'$s edges. Therefore $C$ is an Euler tour.
- First of all, it says that "In order for $G$ not to be an Euler tour, there must be some vertices that $C$ passes through ( since the graph is connected ) but does not exhaust all edges. "
I haven't understood why we have to show that $G$ does not exhaust all edges. In order for $G$ not to be an Euler tour, couldn't it also hold that $G$ traverses an edge more than once?
Then it says that "We have already established that the vertices of a complex cycle have the property that in-degree($v$)=out-degree($v$). Therefore $G'=G-C$ will also have that property."
Why will $G'=G-C$ be a complex cycle, although $G$ isn't necessarily?
Also, could you explain me why it holds that: " If a connected component in a graph has in-degree($v$)=out-degree($v$) then it contains at least one cycle $C'$."
Finally, could you explain me the contradiction?
EDIT: I also want to describe an algorithm that runs in time $O(E)$ and finds an Euler tour of $G$, if it exists. (Hint: Merge edge-disjoint cycles.)
If we apply DFS, we will get a set of cycles formed by disjoint sets of edges, right? But how can we know if it holds that in-degree(v)=out-degree(v), for all vertices in $V$?
Do we have to do something like that? algorithm
Best Answer
In a simple cycle the in degree and the out degree are both one, so if we add to some simple cycle another simple cycle at some vertex, the in degree and the out degree of the vertex will increase both by 1.
You got some wrong concept on $G'$, it is not a complex cycle in fact it doesn't even need to be connected. As we defined cycles in my (algorithmic) dicrete math classes we said that every edge may be traversed at most once so it is not possible that $C$ is a complex cycle which traverses one edge more than once.
So the idea is more that there must be some complex cycle which passes trough every vertex, because your graph is connected, and if uses every edge it is an euler tour. So we take the complex cycle with most edges, and look at $G'=G-C$, as the in degree of some vertex in $G'$ is the in degree of the vertex in $G$ minus the in degree of the vertex in $C$ and the same for the out degrees the graph $G'$ does still have the property, that the in degrees coincide with the out degrees. But if those degrees aren't all $0$ we could add some cycle to $C$ which would result in some complex cycle with more edges, which is some contradiction to our assumption, that $C$ does have the most edges.