Euler’s Theorem
Explore Euler’s theorem and find out which cycle is Eulerian.
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 (denoted In() and Out(), respectively) as the number of edges leading into and out of . A node is balanced if In() = Out(), 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?
The graph in the figure below is balanced but not Eulerian because it’s disconnected, meaning that some nodes can’t be reached from other nodes. In any disconnected graph, it’s impossible to find an Eulerian cycle. In contrast, we say that a directed graph is strongly connected if it’s possible to reach any node from every other node.
We now know that an Eulerian graph must be both balanced and strongly connected. Euler’s Theorem states that these two conditions are sufficient to guarantee that an arbitrary graph is Eulerian. As a result, it implies that we can determine whether a graph is Eulerian without ever having to draw any cycles.
Euler’s Theorem
Every balanced, strongly connected directed graph is Eulerian.
Proof
Let Graph be an arbitrary balanced and strongly connected directed graph. To prove that Graph has an Eulerian cycle, place Leo at any node of Graph (the green node in the figure), and let him randomly walk through the graph under the condition that he can’t traverse the same edge twice.
If Leo were incredibly lucky — or a genius — then he would traverse each edge exactly once and return back to . ...
Get hands-on with 1400+ tech skills courses.