Graph theory · Definition

Eulerian cycle

discrete mathematicsgraphs

Before you start you need to know

It solves the problem of traversing every street, or bridge, of a network without repeating any; it was the origin of graph theory.

Definition

An Eulerian cycle of a graph \(G=(V,E)\) is a cycle that traverses every edge of \(G\) exactly once.

\[G\text{ connected and }\deg(v)\text{ even }\forall v\in V\iff\text{Eulerian cycle exists}\]

In 1736 Euler solved the Königsberg bridges problem: a connected graph has an Eulerian cycle if and only if every vertex has even degree. The reason is local: each time the walk arrives at a vertex it must leave by another edge, so the edges at each vertex pair up. The converse is proved by induction, extracting cycles until the edges run out.

If there are exactly two vertices of odd degree, there is no cycle, but there is an open Eulerian trail starting at one and ending at the other. With more than two odd vertices there is not even that. The Königsberg graph has four vertices of odd degree, so it admits no walk crossing each bridge exactly once.

Guiding example: \(K_5\) is connected and every vertex has degree 4, so it traverses its 10 edges in a cycle; \(K_4\) has degrees 3 and does not allow it. A typical mistake is to confuse it with the Hamiltonian cycle, which visits vertices, not edges: an Eulerian cycle may pass through the same vertex many times. Hierholzer's algorithm builds the cycle in linear time.

Think about it

Which degree condition characterizes a connected graph with an open Eulerian trail?

It has exactly two vertices of odd degree; the trail starts at one and ends at the other.

Exercises 10

  1. Which of these graphs has an Eulerian cycle?
  2. A connected graph has vertex degrees \(2,4,4,6\). Does it have an Eulerian cycle?
  3. \(K_7\) has an Eulerian cycle. How many edges does it traverse?
  4. Which of these complete bipartite graphs has an Eulerian cycle?
  5. A connected graph has exactly two vertices of odd degree. Which statement is true?
  6. A connected graph has six vertices with degrees \(2,2,2,2,4,x\). Which value of \(x\) allows an Eulerian cycle?
  7. If a graph has an Eulerian cycle, which statement is always true?
  8. The Königsberg bridges graph has vertices of degrees \(3,3,3,5\). Why is there no Eulerian cycle?
  9. From \(K_5\) the 4 edges of a cycle \(1\text{-}2\text{-}3\text{-}4\text{-}1\) are removed. What graph remains?
  10. Two connected graphs \(G\) and \(H\) on the same vertex set both have an Eulerian cycle and share no edges. What about their union?

References

  • Kenneth H. Rosen, Discrete Mathematics and Its Applications, 8th edition, McGraw-Hill, 2019. §10.5
  • Susanna S. Epp, Discrete Mathematics with Applications, 5th edition, Cengage, 2019. §10.2
  • Ralph P. Grimaldi, Discrete and Combinatorial Mathematics: An Applied Introduction, 5th edition, Pearson, 2003. §11.5