Problem 815

Let $k\geq 3$ and $n$ be sufficiently large. Is it true that if $G$ is a graph with $n$ vertices and $2n-2$ edges such that every proper induced subgraph has minimum degree $\leq 2$ then $G$ must contain a copy of $C_k$ ?

Source: erdosproblems.com/815

Graph theory

Wiki page

Status

SolvedDisproved

An accepted solution exists. The statement is false.

Disproved. Theorem 1.2 of [NPS17] (Combinatorica 37 (2017), 495--519; refereed; cited from arXiv v1) gives an infinite sequence of degree $3$ -critical graphs with no cycle of length $23$ , so for $k=23$ there is no $n_0$ beyond which every graph of the class contains $C_k$ ; the same construction works for every odd $k\ge23$ (Section 6). The answer is yes for $k=3,4,5$ (Theorem 2 of [EFGS88], recorded as the pending partial claim Erdős, Faudree, Gyárfás and Schelp's Theorem 2) and $k=6$ (Proposition 5.1 of [NPS17]); for $7\le k\le22$ it is not known, and for every even $k\ge8$ it is open (Problem 6.1 of [NPS17], restated as open in a 2026 Combinatorica paper). The site's remark that the question restricted to even $k$ is still open agrees with the sources. The disproof and its acceptance evidence are recorded on the claim page Narins, Pokrovskiy and Szabó's Theorem 1.2, from which the frontmatter is derived.

EFGS88: Erdős, P., Faudree, R. J., Gyárfás, A. and Schelp, R. H., Cycles in graphs without proper subgraphs of minimum degree 3. Eleventh British Combinatorial Conference (London, 1987), Ars Combin. 25B (1988), 195--201. The definition of $G^*(n,m)$ , the Conjecture and the summary of results, p. 195; Lemma 1, Theorem 1, Corollary 1 and Theorem 2, p. 196; the proof of Theorem 2 and Examples 1--3, p. 197; Theorem 5, p. 200; Example 6 and the references, p. 201. Library home: Erdős 1988 (the Rényi archive scan, 7 pp.); paged at Erdős 1988, Conjecture (p. 195), Erdős 1988, Theorem 2 and Erdős 1988, Theorem 5. The reference list of [NPS17] prints the page range as 159--201; the scan's footer prints 195--201.
Er91: Erdős, P., Problems and results in combinatorial analysis and combinatorial number theory. Graph theory, combinatorics, and applications, Vol. 1 (Kalamazoo, MI, 1988), Wiley (1991), 397--406. The passage is recorded from the site's account of it (below).
NPS17: Narins, L., Pokrovskiy, A. and Szabó, T., Graphs without proper subgraphs of minimum degree 3 and short cycles. Combinatorica 37 (2017), no. 3, 495--519, doi:10.1007/s00493-015-3310-9 (published online 10 August 2016, as its Crossref record gives it; the site's reference text gives "Combinatorica (2017), 495-519"); arXiv:1408.5289 (v1, 22 August 2014, 22 pp.; the only arXiv version, with no journal reference in the arXiv record). Conjecture 1.1 and the historical remark, pp. 2--3; Theorem 1.2 and Theorem 1.3, p. 3; Theorem 1.4 and the $C_6$ sentence, p. 4; the construction $G(T)$ and Lemma 2.1, p. 4; Theorem 4.1 and Lemmas 4.2--4.3, pp. 15--16; Proposition 5.1, p. 19; Section 6, p. 21. Library home: Narins, Pokrovskiy and Szabó 2017; paged at Narins, Pokrovskiy and Szabó 2017, Theorem 1.2 and Narins, Pokrovskiy and Szabó 2017, Theorem 1.4.
BoBr89: Bollobás, B. and Brightwell, G., Long cycles in graphs with no subgraphs of minimal degree 3. Discrete Math. 75 (1989), 47--53. Cited by [NPS17] (p. 2) for the term "degree $3$ -critical" and for the order of the longest cycle. Context; not cited by the site.
DKMMZ26: Di Braccio, F., Katsamaktsis, K., Ma, J., Malekshahian, A. and Zhao, Z., Leaf-to-leaf paths and cycles in degree-critical graphs. Combinatorica 46 (2026), article 11, doi:10.1007/s00493-026-00205-2 (the journal reference on the arXiv record); arXiv:2504.11656 (v2, 4 March 2026, marked "Journal version", 24 pp.; on its card Dibraccio 2026). Theorem 1, p. 2; the account of the earlier results, p. 2; Problem F, p. 22. Context; not cited by the site.

Problem 815

Status

Proof claims

Discussion