MHB Proof of Euler Tour in Graphs: In-degree($v$)=Out-Degree($v$)

[evinda]

Hello! (Wave)

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: https://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 comlex 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 edge 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?

 

[evinda]

I have also asked it here: The graph has an Euler tour iff in-degree($v$)=out-degree($v$) and I have understood it.

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?

Initialization(G)
    1. for each edge in G.E 
    2.      e.color=WHITE
    3. DFS(G)

    DFS(G)
    1. for each vertex u in G.V
    2.      u.color=WHITE
    3. for each vertex u in G.V
    4.      if u.color==WHITE
    5.            DFS-VISIT(G, u)

  

     DFS-VISIT(G, u)
        1. u.color=GRAY
        2. for each v in G.Adj[u]
        3.      if (v.color==WHITE && (u,v).color==WHITE)
        4.          (u,v).color=GRAY
        5.          DFS-VISIT(G, v) 
        6. u.color=BLACK