Tournaments and Even Graphs are Equinumerous

Gordon F. Royle, Cheryl E. Praeger, S. P. Glasby, Saul D. Freedman, Alice Devillers

Published 2022-04-05Version 1

A graph is called \emph{odd} if there is an orientation of its edges and an automorphism that reverses the sense of an odd number of its edges, and \emph{even} otherwise. Pontus von Br\"omssen (n\'e Andersson) showed that the existence of such an automorphism is independent of the orientation, and considered the question of counting pairwise non-isomorphic even graphs. Based on computational evidence, he made the rather surprising conjecture that the number of pairwise non-isomorphic \emph{even graphs} on $n$ vertices is equal to the number of pairwise non-isomorphic \emph{tournaments} on $n$ vertices. We prove this conjecture using a counting argument with several applications of the Cauchy-Frobenius Theorem.