Problem 1006

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?

Source: erdosproblems.com/1006

Graph theory
Cycles

Wiki page

Status

SolvedDisproved

An accepted solution exists. The statement is false.

Disproved. Corollary 3 of Nešetřil and Rödl [NeRo78b] (Proc. Amer. Math. Soc. 72 (1978), 417--421; refereed) gives, for every $s$ , a graph with no cycle of length less than $s$ which under every ordering of its vertices contains a monotone path $v_1v_2\cdots v_s$ , $v_1<\dots<v_s$ , closed into an $s$ -cycle by the edge $v_1v_s$ . With $s=5$ this is a graph of girth five with no orientation of the required kind; the deduction is written out below and is this page's own. Corollary 4 of the same paper states the Hasse-diagram form. The paper describes its result as "the full solution of an Erdös-Ore problem" and cites Erdős's 1971 list for the question. The claim page Nešetřil and Rödl 1978 records the result, its postings and the acceptance evidence. O. Pretzel, "A non-covering graph of girth six" (Discrete Math. 63 (1987), 241--244; stated from its zbMATH summary and pending), constructs a graph of girth six that is not a cover graph, an explicit negative answer through the equivalence in the Formulation, recorded on Pretzel 1987. The standing in the frontmatter is derived from the claim pages.

NeRo78b: Nešetřil, Jaroslav and Rödl, Vojtěch, On a probabilistic graph-theoretical method. Proc. Amer. Math. Soc. 72 (1978), no. 2, 417--421, doi:10.1090/S0002-9939-1978-0507350-7 (received 20 May 1977, revised 6 January 1978; Crossref record). Corollary 3 and Figure 1, p. 419; Corollary 4, p. 419, with its one-sentence proof on p. 420; Theorem 2, pp. 418--419. Library home: Nešetřil and Rödl 1978; paged at Nešetřil and Rödl 1978, Corollary 3 and Nešetřil and Rödl 1978, Corollary 4.
Er71: Erdős, P., Some unsolved problems in graph theory and combinatorial analysis. Combinatorial Mathematics and its Applications (Proc. Conf., Oxford, 1969) (1971), 97--109; item 7, p. 99, with Figure 1 (the Grötzsch graph) on p. 100. Library home: Erdős 1971; the item is paged at Erdős 1971, Item 7 (pp. 99-100).
Er76b: Erdős, P., Problems and results in graph theory and combinatorial analysis. Proceedings of the Fifth British Combinatorial Conference (Univ. Aberdeen, Aberdeen, 1975), Congr. Numer. XV (1976), 169--192; Problem 8, p. 175 (the site's reference text for the key, 2026-09-18). Library home: Erdős 1976 (a Rényi archive scan); paged at Erdős 1976, Problem 8.

Problem 1006

Status

Proof claims

Discussion