Euler’s Theorem

We’ll now explore Euler’s method for solving the Eulerian Cycle Problem. Euler worked with undirected graphs like Königsberg, but we’ll consider an analogue of his algorithm for directed graphs so that his method will apply to genome assembly.

Balanced and unbalanced graph

Consider an ant, whom we’ll call Leo, walking along the edges of an Eulerian cycle. Every time Leo enters a node of this graph by an edge, he’s able to leave this node by another unused edge. Thus, in order for a graph to be Eulerian, the number of incoming edges at any node must be equal to the number of outgoing edges at that node. We define the indegree and outdegree of a node $v$ (denoted In($v$) and Out($v$), respectively) as the number of edges leading into and out of $v$. A node $v$ is balanced if In($v$) = Out($v$), and a graph is balanced if all its nodes are balanced. Because Leo must always be able to leave a node by an unused edge, any Eulerian graph must be balanced. The figure below shows a balanced graph and an unbalanced graph.

STOP and Think: We now know that every Eulerian graph is balanced; is every balanced graph Eulerian?