Tags: #definition

Eulerian cycle

A Eulerian cycle (or circuit, tour, walk) is a walk on a finite directed graph $G=(V,E)$ such that you walk on every edge exactly once and you end where you started.
Alternatively, you may view this as an ordering of all the edges without repetitions.

Properties

G has a Eulerian cycle if and only if the following two conditions are true:

• $G$ is connected (as an undirected graph)
• $\mathrm{\forall }v\in V,\mathrm{indeg}(v)=\mathrm{outdeg}(v)$
  $(⟹)$ is clear, and $(⟸)$ can be constructed by starting at some vertex and performing a random walk (going through each edge once) until it terminates. Because of the second condition, this walk has to end where it started. If this is not an Eulerian cycle, then take any edge that is connected to this walk that hasn't been chosen and do a random walk starting from there. Iterate. We are guaranteed to hit every vertex and edge as the graph is connected. Furthermore, together (gluing them appropriately) these form an Eulerian cycle.

The BEST theorem counts the number of Eulerian cycles on a graph