Graph-theory open problems

Ádám's Conjecture

High ★★★ Graph Theory » Directed Graphs
Author: Ádám, András— posted by fhavet on 2013-03-01

Status disproved high confidence

Thomassen (2023) disproves Ádám's conjecture for simple digraphs by constructing an infinite family of strongly 2-connected oriented graphs (directed graphs with no multiple arcs) in which no arc reversal decreases the number of directed cycles. This extends the earlier counterexamples (Grinberg, Jirásek, Thomassen 1987), which were only for multigraphs, to the realm of simple digraphs. The weaker tournament version of the conjecture ('every non-transitive tournament has an arc whose reversal reduces the number of directed cycles') appears to remain open.

Cited literature (1)

  • counterexample Ádám's conjecture (2023)
    Carsten Thomassen · Journal of Combinatorial Theory, Series B · doi:10.1016/j.jctb.2023.01.005

    Constructs an infinite family of strongly 2-connected oriented graphs (simple digraphs, no multiple arcs) in which no single arc reversal decreases the number of directed cycles, thereby disproving Ádám's conjecture for simple digraphs.

Reviewer notes. The ScienceDirect page (https://www.sciencedirect.com/science/article/pii/S0095895623000060) for the Thomassen 2023 paper returned HTTP 403 Forbidden. Verification was completed via the DTU Research Database page, which confirmed title, author, year, journal, volume (161), pages (15–20), DOI (10.1016/j.jctb.2023.01.005), and abstract. No arXiv preprint of the Thomassen 2023 paper was found. The tournament variant of the conjecture ('every non-transitive tournament has an arc whose reversal reduces the number of directed cycles') does not appear to be addressed by Thomassen 2023, since strongly 2-connected oriented graph counterexamples need not be tournaments; that variant appears to remain open.

Auto-reviewed 2026-05-08 with claude-sonnet-4-6 (web search enabled) · 135s.

Conjecture. Every digraph with at least one directed cycle has an arc whose reversal reduces the number of directed cycles.

Discussion

The conjecture fails for multigraphs (multiple arcs are allowed). Counterexamples for multidigraphs have been given by Grinberg [G], Jirásek [J] and Thomassen [T]. Surprisingly, the conjecture remains open for tournaments. Conjecture Every tournament that is not transitive has an arc whose reversal reduces the number of directed cycles.

Bibliography

  • ★ [A] A. Ádám, Problem 2. In Theory of Graphs and its Applications (M. Fiedler, ed.), 234. (1964) Publishing House of the Czechoslovak Academy of Sciences, Prague.
  • [G] E.Y. Grinberg, Examples of non-Ádám multigraphs (in Russian) Latv. Mat. Ezhegodnik, 31 (1988), pp. 128–138
  • [J] J. Jirásek, On a certain class of multidigraphs, for which reversal of no arc decreases the number of their cycles, Comment. Math. Univ. Carolinae, 28 (1987), pp. 185–189.
  • [T] C. Thomassen, Counterexamples to Ádám's conjecture on arc reversals in directed graphs, J. Combin. Theory Ser. B, 42 (1987), pp. 128–130.