DISPROVED
This has been solved in the negative.
Let $G$ be a graph with girth $>4$ (that is, it contains no cycles of length $3$ or $4$). Can the edges of $G$ always be directed such that there is no directed cycle, and reversing the direction of any edge also creates no directed cycle?
In
[Er71] Erdős credits this problem to Ore, who gave an example of a graph without this property which has girth $4$. Gallai noted that the
Grötzsch graph also lacks this property.
This is false - Nešetřil and Rödl
[NeRo78b] proved that, for every integer $g$, there is a graph $G$ with girth $g$ such that every orientation of the edges in $G$ contains a directed cycle or a cycle obtained from a directed cycle by reversing one directed edge.
View the LaTeX source
This page was last edited 02 December 2025. View history
|
Likes this problem
|
None
|
|
Interested in collaborating
|
None
|
|
Currently working on this problem
|
None
|
|
This problem looks difficult
|
None
|
|
This problem looks tractable
|
None
|
|
The results on this problem could be formalisable
|
None
|
|
I am working on formalising the results on this problem
|
None
|
Additional thanks to: Boris Alexeev and Raphael Steiner
When referring to this problem, please use the original sources of Erdős. If you wish to acknowledge this website, the recommended citation format is:
T. F. Bloom, Erdős Problem #1006, https://www.erdosproblems.com/1006, accessed 2026-04-11
