Tournaments and even graphs are equinumerous

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

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review


A graph is called odd if there is an orientation of its edges and an automorphism that reverses the sense of an odd number of its edges and even otherwise. Pontus von Brömssen (né 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 even graphs on n vertices is equal to the number of pairwise non-isomorphic tournaments on n vertices. We prove this conjecture using a counting argument with several applications of the Cauchy–Frobenius theorem.
Original languageEnglish
Pages (from-to)515-524
Number of pages10
JournalJournal of Algebraic Combinatorics
Early online date29 Dec 2022
Publication statusPublished - 1 Mar 2023


  • Tournaments
  • Graph counting
  • Graph enumeration
  • Graph automorphisms
  • Graph isomorphisms
  • Cauchy-Frobenius theorem


Dive into the research topics of 'Tournaments and even graphs are equinumerous'. Together they form a unique fingerprint.

Cite this