Introduction to Graph Theory · Problem 5.24

Trees and arborescences — Darij Grinberg

Mathematics — Graph Theory · eulerian-circuits-complete-graph-divisibility

Problem

Let

n = 2m + 1 > 2

be an odd integer. Let

e

be an edge of the (undirected) complete graph

K_n

. Prove that the

\#

of Eulerian circuits of

K_n

that start with

e

is a multiple of

(m-1)!^n

. [Hint: Argue that each Eulerian circuit of

K_n

is an Eulerian circuit of a unique balanced tournament. Here, a ``balanced tournament'' means a balanced digraph obtained from

K_n

by orienting each edge.]