Problem 1012

Let $k\geq 0$ . Let $f(k)$ be such that every graph on $n\geq f(k)$ vertices with at least $\binom{n-k-1}{2}+\binom{k+2}{2}+1$ edges contains a cycle on $n-k$ vertices. Determine or estimate $f(k)$ .

Source: erdosproblems.com/1012

Graph theory

Wiki page

Status

SolvedAnswered

An accepted solution exists. Settled in another form, for example when its parts resolve differently or the question is open-ended.

Solved. Woodall's Corollary 11.1 [Wo72] (Proc. London Math. Soc. (3) 24 (1972), 739--755; printed p. 749): a graph on $n\ge r+3$ vertices with at least $\binom{n-r-1}2+\binom{r+2}2+1$ edges when $n\ge2r+3$ , or at least $[\frac14n^2]+1$ edges when $n<2r+3$ , contains a circuit of length $d$ for every $3\le d\le n-r$ ; with $r=k$ the first bound is this problem's count and $d=n-k$ is in range, so $f(k)=2k+3$ works for every $k\ge0$ , and the paper states (p. 749) that the first bound is the least possible because its $G_4(n,r)$ , the sharing-vertex graph, has no circuit of length $n-r$ or more. The paper introduces the corollary as the answer to Erdős's 1969 question (pp. 741 and 749, citing Problem 4 of [Er71]). Theorem 8 of Li and Ning [LiNi23] (Electron. J. Combin. 30 (2023), P1.39; refereed, open access; p. 4) restates the $n\ge2k+3$ half with the same count and range, and records that the sharing-vertex graph shows the count is sharp, "which means that $\mathrm{ex}(n,C_{n-k})=\binom{n-k-1}2+\binom{k+2}2$ for $n\ge2k+3$ ". The status rests on the original's statement and the structure of its proof of Theorem 11, with the refereed restatement and the site's account (which records Woodall's theorem as settling the question completely) agreeing. The smallest admissible $f(k)$ : the corollary's second bound covers $k+3\le n\le2k+2$ , and this problem's count is at least $[\frac14n^2]+1$ there (an elementary comparison recorded on the library's result page as a filing observation), so the implication holds for every $n\ge k+3$ and is vacuous for $n\le k+2$ , where the count exceeds $\binom n2$ ; the thread's reading that no $n$ fails rests on the printed corollary plus that comparison, and nothing is independently reviewed. The claim page Woodall records the result, its acceptance evidence and its postings, and the standing derives from it. The site also credits Ore [Or61] with $f(0)=1$ (an accepted partial claim, Ore 1961; Theorem 4.3, p. 320, states the threshold $\binom{n-1}2+2$ with its sharpness, and Erdős's 1962 note quotes it) and Bondy [Bo71b] with $f(1)=1$ (an accepted partial claim, Bondy 1971; Theorem 2, p. 125, states that a graph of order $n$ and size at least $\frac12(n^2-5n+14)=\binom{n-2}2+4$ has a cycle of length $n-1$ , printed without a range for $n$ ), and says the existence of $f(k)$ follows from Erdős's 1962 theorem [Er62e] by an argument given in the thread (recorded below with its provenance).

Wo72: Woodall, D. R., Sufficient conditions for circuits in graphs. Proc. London Math. Soc. (3) 24 (1972), no. 4, 739--755, doi:10.1112/plms/s3-24.4.739 (Crossref record: issued May 1972, online at the publisher since December 2016). Corollary 11.1, printed p. 749: a graph on $n\ge r+3$ vertices with at least $\binom{n-r-1}2+\binom{r+2}2+1$ edges when $n\ge2r+3$ , or $[\frac14n^2]+1$ edges when $n<2r+3$ , contains a circuit of every length from $3$ to $n-r$ ; the case $k=0$ of Theorem 11 (pp. 747--748), whose proof (pp. 748--749) is followed at the level of its case structure. The example $G_4(n,r)$ and the attribution of the question to Erdős, p. 741. Library home: Woodall 1972; the corollary is paged at Woodall 1972, Corollary 11.1.
LiNi23: Li, Binlong and Ning, Bo, Stability of Woodall's theorem and spectral conditions for large cycles. Electron. J. Combin. 30 (2023), no. 1, Paper No. 1.39, doi:10.37236/11641 (submitted 1 November 2022, accepted 13 February 2023, published 24 February 2023; open access, CC BY-ND). Theorem 8 (Woodall), p. 4; the sharpness sentence and the introduction's survey, pp. 2--3. Filed as Li and Ning 2023 (a lead used for the attestation; the paper's own results are spectral and not this problem's).
Er62e: Erdős, P., Remarks on a paper of Pósa. Magyar Tud. Akad. Mat. Kutató Int. Közl. 7 (1962), 227--229; the Theorem, p. 227. Library home: Erdős 1962 (a Rényi archive scan); paged at Erdős 1962, Theorem (p. 227).
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 4, p. 98. Library home: Erdős 1971 (the Rényi archive's scan); the item is paged at Erdős 1971, Item 4 (p. 98).
Or61: Ore, Oystein, Arc coverings of graphs. Ann. Mat. Pura Appl. (4) 55 (1961), no. 1, 315--321, doi:10.1007/BF02412090 (Crossref record). Theorem 4.3, printed p. 320: "A graph with $\nu_e(G)\ge\frac12(n-1)(n-2)+2$ edges has a Hamilton circuit. When $\nu_e(G)=\frac12(n-1)(n-2)+1$ the only graph without a Hamilton circuit consists of a complete graph, $U_{n-1}$ and a single edge connecting it with an outside vertex; in addition, for $n=5$ there is the exceptional graph depicted in Fig. 3." Its proof (pp. 320--321) rests on Ore's 1960 degree theorem, the paper's Theorem 3.2. The statement is the one quoted on p. 227 of [Er62e]: "ORE [2] proved that if $l\ge\binom{n-1}2+2$ then every $G^{(n)}_l$ is Hamiltonian, and he showed that the result is false for $l=\binom{n-1}2+1$ ." Library home: Ore 1961; the theorem is paged at Ore 1961, Theorem 4.3.
Bo71b: Bondy, J. A., Large cycles in graphs. Discrete Math. 1 (1971/72), no. 2, 121--132, doi:10.1016/0012-365X(71)90019-7 (Crossref record; the publisher's open-archive license dated 2013; the article is in the publisher's open archive). Theorem 2, printed p. 125 (PDF p. 5 of the open-archive file): "Let $G$ have order $n$ and size at least $\frac12(n^2-5n+14)$ . Then $G$ has a cycle of length $n-1$ ", followed by the attribution of the conjecture to Erdős at the Oxford conference of July 1969 and the sharpness graph of complete blocks of orders $n-2$ and $3$ ; its proof (p. 127) rests on Ore's theorem, Pósa's degree condition and the theorem of Bondy's pancyclic paper. Conjecture 1 (p. 126), $f(r,n)=g(r,n)$ for $r\le\frac12(n-1)$ with $g(r,n)=\frac12\{n^2-(2r+1)n+2r^2+2r+2\}$ , is this problem at $r=k+1$ , and p. 128 states that it holds for all $n\ge\frac12(r^2+5r+4)$ . [LiNi23] (p. 2) writes that "At almost the same time, some partial result was also obtained by Bondy [4]". Library home: Bondy 1971; the theorem is paged at Bondy 1971, Theorem 2 and the conjecture with its range at Bondy 1971, Conjecture 1.

Problem 1012

Status

Proof claims

Discussion