Woodall 1972 sufficient conditions circuits graphs

../

corollary_11_1: Woodall's answer to Erdős's 1969 question: a graph on n ≥ 2r + 3 vertices with at least C(n − r − 1, 2) + C(r + 2, 2) + 1 edges contains a circuit of every length from 3 to n − r, and a graph on r + 3 ≤ n < 2r + 3 vertices with at least [n²/4] + 1 edges does too; the first bound is sharp by a complete (n − r − 1)-gon and a complete (r + 2)-gon sharing one vertex. Problem 1012's f(k) ≤ 2k + 3, with the small range covered as well.

theorem_11: Woodall's main undirected theorem: a graph on n ≥ r + 3 vertices, each of valency at least k, contains a circuit of every length from 3 to n − r once its number of edges reaches the bound of its case, the cases split by whether n ≥ 2r + 3 and by the size of k, each bound least possible.

theorem_2d: Woodall's directed form of Ore's theorem: a directed graph on n ≥ 2 vertices in which the out-valency of a plus the in-valency of b is at least n for every two distinct vertices a, b with no edge from a to b has a directed Hamiltonian circuit.

---

D. R. Woodall, 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 (the publisher's record; the foot of p. 739 prints the journal, series, volume, year and pages). Received 20 August 1970, revised 19 January 1971 (p. 739); the author at the Department of Mathematics, University of Nottingham (p. 755); the research "sponsored in part by the Science Research Council of the United Kingdom" (footnote, p. 739). Cited as [Wo72] on the problem page. The edition cited is the publisher's version of record at https://doi.org/10.1112/plms/s3-24.4.739; no preprint or other version is known here. Its seventeen references (pp. 754--755) include [1] Bondy, Pancyclic graphs I, filed as bondy_1971_pancyclic_graphs_i; [2] Bondy, Large cycles in graphs, "to appear", filed as bondy_1971_large_cycles_graphs; [4] Erdős, Remarks on a paper of Pósa, filed as erdos_1962_remarks_paper_posa; [5] Erdős, Unsolved problems in graph theory and combinatorial analysis, the Oxford proceedings, filed as erdos_1971_unsolved_problems_graph_theory_combinatorial_analysis; [6] Erdős and Gallai, On maximal paths and circuits of graphs, filed as erdos_1959_maximal_paths_circuits_graphs; and [14] Ore, Arc coverings of graphs, filed as ore_1961_arc_coverings_graphs. The others are Dirac 1952, Ghouila-Houri 1960, Harary 1969, Harary and Moser 1966, Nash-Williams 1966 and 1969, Newman 1958, Ore 1960, Pósa 1962 and 1963, and Rédei 1934, none held.

The copy read for this card is the publisher's file for the article: 17 pages, printed pp. 739--755 = PDF pp. 1--17 (printed p. $n$ is PDF p. $n-738$), a scan of the printed pages with an OCR text layer (the file's metadata names ABBYY FineReader and a July 2006 creation date, and a later pass added the publisher's download stamp, which prints the journal's identifier, the DOI, the downloading account holder's name and the download date down the outer margin of PDF pp. 2--17, printed pp. 740--755; PDF p. 1, printed p. 739, is unstamped, checked in the text layer of every page and on the page images of PDF pp. 1--2 on 2026-09-23). The text layer locates passages and reads the prose, but garbles the displays: binomial coefficients, the integer-part brackets, subscripts and the inequality signs. Provenance: obtained from the publisher on 2026-09-22 as a DRM-free PDF through the library's acquisition, from https://doi.org/10.1112/plms/s3-24.4.739; 1,107,899 bytes. No copyright line is printed on the 1972 pages; the publisher's download footer reads "See the Terms and Conditions (https://onlinelibrary.wiley.com/terms-and-conditions) on Wiley Online Library for rules of use; OA articles are governed by the applicable Creative Commons License" and the article carries no open-access marker, the publisher's article page could not be read on 2026-10-02 (it answered HTTP 403), and the Crossref record (read 2026-10-07) names the publisher's text and data mining terms and its terms and conditions for the version of record and no Creative Commons license, every other right reserved.

Read status: claims checked for the summary and the footnote (p. 739), the definitions of path, circuit, length, Hamiltonian, connected and cut-vertex and the integer convention (p. 740), the five example graphs $G_1,\ldots,G_5$ with the sentence attributing the question to Erdős (pp. 740--741), Theorems 1--4 with the display for $f(n,k)$ (pp. 741--742), Theorems 5 and 6 (p. 742), the definition of pancyclic, Theorems 8 and 9 and Corollaries 8.1, 8.2, 9.1 and 9.2 (pp. 744--745), Theorem 10, Lemma 11.1 and Sublemma 11.2.1 (p. 745), Lemma 11.2 (p. 746), the Conjecture, the displays for $f(n,k)$ and $f(n,k,r)$ and Theorem 11 with its case list and bounds (pp. 747--748), the sentence answering Erdős's question and Corollary 11.1 with its sharpness parenthesis (p. 749), each read clause by clause on the page images of PDF pp. 1--4 and 6--11 (printed pp. 739--742 and 744--749) on 2026-09-22. Printed p. 743 (PDF p. 5; Theorem 7 and its proof), § 6 on directed graphs (pp. 749--754), the acknowledgment and the reference list (pp. 754--755) were read in the text layer for structure only; the statements of Theorem 7 and of § 6 as summarized below, and the reference list, were checked against the page images, and Theorem 2D with the remarks of § 6 that frame it (pp. 749--751) was read clause by clause on the page images on 2026-10-08, its proof (pp. 751--754) for structure only. The proofs of Lemma 11.1, Sublemma 11.2.1, Lemma 11.2 and Theorem 11 (pp. 745--749) were read in full on the page images and their structure followed; their inequalities were not checked. Nothing here is independently reviewed.

Contents

• Summary and § 1, Definitions (pp. 739--740, page images). The summary says that lower bounds on vertex valencies, on the number of edges, or on both, can force a circuit of at least, or of exactly, a specified length; that the paper lists many such theorems, old and new; that its culminating undirected result gives the number of edges a graph on $n$ vertices with minimum valency at least $k$ needs to force a circuit of length exactly $n-r$, Erdős having posed the case $k=0$ as an unsolved problem in 1969 (the paper's [5]); and that its main directed result is a directed form of Ore's theorem. Graphs are finite without loops or multiple edges; $\rho(a)$ is the valency of $a$, and in a directed graph $\rho_{\mathrm{out}}(a)$ and $\rho_{\mathrm{in}}(a)$ count the edges leaving and entering $a$; a path has distinct vertices, a circuit is a path closed by one more edge, and the length is the number of edges, so a circuit in an undirected graph has length at least $3$. An italic letter that stands for a number is a non-negative integer, and $[\alpha]$ is the integer part.
• § 2, Undirected graphs: examples (pp. 740--741, page images). The paper says every result stated is best possible in a sense, and collects the witnesses here. $G_1(n,k)$, for $0<k<\frac12n$: $k$ independent vertices, each joined to the same $k$ vertices of a complete graph on $n-k$ further vertices; $\binom{n-k}2+k^2$ edges, minimum valency $k$, not Hamiltonian. $G_2(n,d)$, for $n=k(d-1)+1$ with $k>0$ and $d>1$: $k$ complete $d$-gons sharing exactly one common vertex; $\frac12d(n-1)$ edges, minimum valency $d-1$, no circuit of length $d+1$ or more. $G_3(n)$: the complete bipartite graph with parts of $[\frac12n]$ and $n-[\frac12n]$ vertices; $[\frac14n^2]$ edges, no odd circuit, every even length from $4$ to $2[\frac12n]$. $G_4(n,r)$, for $r\ge0$ and $n\ge2r+3$: complete graphs on $n-r-1$ and on $r+2$ vertices that share exactly one vertex; $\binom{n-r-1}2+\binom{r+2}2$ edges, minimum valency $r+1$, no circuit of length $n-r$ or more. Here the paper records the question it goes on to answer: "In 1969 Erdös asked whether a graph on $n$ vertices, with more edges than $G_4(n,r)$, must contain a circuit of length $n-r$ (see [5], Problem 4)" (p. 741), and adds that Corollary 11.1 shows that it must. $G_5(n,k,r)$, for $n\ge2k+r+1$ and $k>0$: $k+r$ independent vertices, each joined to the same $k$ vertices of a complete graph on $n-k-r$ further vertices; $\binom{n-k-r}2+k(k+r)$ edges, minimum valency $k$, no circuit of length $n-r$ or more; $G_5(n,k,0)=G_1(n,k)$.
• § 3, Results about Hamiltonian circuits (pp. 741--742, page images), for $G$ on $n\ge3$ vertices. Theorem 1 (Dirac): minimum valency $\frac12n$. Theorem 2 (Ore): $\rho(a)+\rho(b)\ge n$ for every nonadjacent pair. Theorem 3 (Pósa, as simplified by Nash-Williams): at most $j-1$ vertices of valency at most $j$ when $j<\frac12(n-1)$, and at most $j$ when $j=\frac12(n-1)$. Theorem 4 (Erdős [4]): minimum valency $k$ and either $k\ge\frac12n$ or at least $f(n,k)=\max\{\binom{n-k}2+k^2+1,\binom{[\frac12(n+2)]}2+[\frac12(n-1)]^2+1\}$ edges, the Theorem of Erdős 1962; the paper proves it on p. 742 by checking the hypotheses of Theorem 3. Theorems 1, 3 and 4 are sharp by $G_1$, and Theorem 2 by $G_1$ for odd $n$ and in general by any $G_4(n,r)$.
• § 4, Circuits of at least a specified length (pp. 742--743, page images). Theorem 5 (Dirac): minimum valency $d>1$ gives a circuit of length at least $d+1$. Theorem 6 (new): $\rho(a)+\rho(b)\ge2d-1$ for every nonadjacent pair, on $n\ge d+1\ge3$ vertices, gives a circuit of length at least $d+1$; a corollary of the directed Theorem 6D. Theorem 7 (Erdős and Gallai [6], Theorem (2.7)): for $d>1$, at least $\frac12d(n-1)+1$ edges give a circuit of length at least $d+1$; the paper gives a new proof by induction on $n$.
• § 5, Circuits of exactly a specified length (pp. 744--749, page images). A graph on $n$ vertices is pancyclic when it has a circuit of every length from $3$ to $n$. Theorem 8 (Bondy [1]): a Hamiltonian graph with at least $\frac14n^2$ edges is pancyclic or is $G_3(n)$ with $n$ even. Corollary 8.1: under Theorem 1 or Theorem 2 the same conclusion, and in either case every even length from $4$ to $n$. Corollary 8.2: pancyclic under any of (1) minimum valency at least $\frac12(n+1)$, (2) $\rho(a)+\rho(b)\ge n+1$ ($n$ even) or $\ge n$ ($n$ odd) for nonadjacent pairs, (3) minimum valency $k$ and the edge bound of Theorem 4. Theorem 9 (Bondy [2], Corollary 3.1): at least $\frac14(k(2n-k)+1)$ edges and a longest circuit of length $k$ give every length from $3$ to $k$. Corollary 9.1: $[\frac14n^2]+1$ edges and a circuit of length $k$ give every length from $3$ to $k$. Corollary 9.2: $[\frac14n^2]+1$ edges on $n\ge3$ vertices give every length from $3$ to $[\frac12(n+3)]$. Theorem 10 (Dirac): a connected graph on at least $2k$ vertices with no cut-vertex and minimum valency $k>1$ has a circuit of length at least $2k$. Lemma 11.1: $\binom{n-k}2+\binom{k+1}2+1$ edges with minimum valency $k$ give a connected graph without a cut-vertex. Sublemma 11.2.1: $\binom{n-k}2+\binom{k+1}2$ edges, minimum valency $k$ and a path on at least $h+1\ge4$ vertices give a circuit of every length from $3$ to $h$; the paper credits the completion of the proof to the referee (p. 746). Lemma 11.2: on $n\ge r+3$ vertices, with the edge bound of Lemma 11.1, minimum valency $k$ and at most $j+r-1$ vertices of valency at most $j$ when $j<\frac12(n-r-1)$ (at most $j+r$ when $j=\frac12(n-r-1)$), a circuit of every length from $3$ to $n-r$; proved by induction on $r$ through a graph with one added vertex joined to all others and Sublemma 11.2.1. A Conjecture (p. 747) would extend Pósa's theorem: a connected graph without a cut-vertex whose low-valency counts obey the Lemma 11.2 condition has a circuit of length at least $n-r$. The main theorem, Theorem 11 (pp. 747--748), with $f(n,k)=\binom{n-k}2+\binom{k+1}2$ and $f(n,k,r)=\binom{n-k-r}2+k(k+r)$: a graph on $n\ge r+3$ vertices with minimum valency $k$ has a circuit of every length from $3$ to $n-r$ once it has the number of edges of its case. Case A, $n\ge2r+3$: A1, $k\le r+1$, $f(n,r+1)+1$; A2, $r+1\le k<\frac12(n-r)$, $\max\{f(n,k),f(n,k,r),f(n,[\frac12(n-r-1)],r)\}+1$; A3, $\max\{r+1,\frac12(n-r)\}\le k<\frac12n$, $f(n,k)+1$; A4, $k=\frac12n$, $[\frac14n^2]+1$; A5, $k>\frac12n$, no bound. Case B, $n<2r+3$: B1, $k\le\frac12n$, $[\frac14n^2]+1$; B2, $k>\frac12n$, no bound. The paper states that each bound is least possible, by $G_4(n,r)$ for A1, by $G_4(n,k-1)$, $G_5(n,k,r)$ and $G_5(n,[\frac12(n-r-1)],r)$ for A2, by $G_4(n,k-1)$ for A3 and by $G_3(n)$ for A4 and B1; that the bounds stay best possible for a circuit of length exactly $n-r$, except that A4 and B1 might improve when $n-r$ is even; and that for a circuit of length at least $n-r$ the A4 and B1 bounds drop (no bound at $k=\frac12n$ by Theorem 1, none for $k\ge n-r-1$ by Theorem 5, and $\frac12(n-r-1)(n-1)+1$ by Theorem 7). Proof (pp. 748--749): A5 and B2 from Corollary 8.2 (1); A4 from Theorem 1 and Corollary 9.1; B1 from Corollary 9.2; A3 from Lemma 11.1, Theorem 10 and Corollary 9.1; A2 by checking the hypotheses of Lemma 11.2 as in the proof of Theorem 4; A1 by induction on $r$, with $r=0$ from Corollary 8.2 (3) and the step removing a vertex of valency $k\le r+1$. Corollary 11.1 (p. 749) is the case $k=0$, introduced as the answer to Erdős's question, with the note that Bondy ([2], Theorem 2) settled the case $r=1$ and that the case $r=0$ is the case $k=1$ of Theorem 4, noted earlier by Ore [14]; paged at corollary_11_1.
• § 6, Directed graphs (pp. 749--754, page images). The Rédei and Harary--Moser theorem on directed graphs in which every two vertices are joined in at least one direction; Theorem 1D (Ghouila-Houri) and Corollary 1D.1; Conjecture 3D (Nash-Williams), a directed Pósa condition; Theorem 5D, minimum out-valency $d>0$ gives a directed circuit of length at least $d+1$; Theorem 6D, $\rho_{\mathrm{out}}(a)+\rho_{\mathrm{in}}(b)\ge2d-1$ for every ordered pair of distinct vertices with $a$ not joined to $b$, on $n\ge d+1\ge2$ vertices, gives a directed circuit of length at least $d+1$; and the section's main result, Theorem 2D, the directed form of Ore's theorem: $\rho_{\mathrm{out}}(a)+\rho_{\mathrm{in}}(b)\ge n$ for every such pair, on $n\ge2$ vertices, gives a directed Hamiltonian circuit, proved through Lemmas 2D.1--2D.3 by extending a longest circuit.
• Acknowledgment (p. 754) to the referee, and References 1--17 (pp. 754--755), listed above.
• Translation to Problem 1012's letters. The problem's $k$ is the paper's $r$, and the paper's $k$ is the minimum valency, $0$ in Corollary 11.1. The first bound of Corollary 11.1 at $r=k$ is the problem's edge count $\binom{n-k-1}2+\binom{k+2}2+1$, its range $n\ge2k+3$ is the site's, and its conclusion includes the length $d=n-k$; $G_4(n,k)$ is the problem's sharpness graph, $K_{n-k-1}$ and $K_{k+2}$ sharing one vertex. The second bound covers $k+3\le n<2k+3$; the result page compares it with the problem's count.
• Filing observations, not review verdicts. (1) The edge bound of Lemma 11.2 (p. 746) reads on the page image as $\binom{n+k}2+\binom{k+1}2+1$, where Lemma 11.1 and Sublemma 11.2.1 print $\binom{n-k}2$; with a plus sign the hypothesis exceeds $\binom n2$ for $k>0$, the induction in its proof replaces $n,k$ by $n+1,k+1$, which preserves $n-k$, and Theorem 11's proof feeds it the A2 bound built from $f(n,k)=\binom{n-k}2+\binom{k+1}2$; the sign is read here as a misprint for $n-k$. (2) Corollary 11.1 prints two conditions for each regime, $n\ge2r+3$ and $n-r\ge\frac12(n+3)$ for the first and their negations for the second; the two are the same inequality rearranged. (3) The summary's text layer reads "$h=0$" where the page image reads $k=0$. (4) The paper uses the name $f(n,k)$ twice: on p. 742 for Theorem 4's bound, a maximum of two terms, and on p. 747 for $\binom{n-k}2+\binom{k+1}2$; Theorem 11 and Corollary 11.1 use the second. (5) The download stamp on PDF pp. 2--17 of the copy read carried the downloading account holder's name down the outer margin, and the byte count above is that stamped copy's.

Compiled scope

The paper is compiled at statement depth for the result Problem 1012 consumes: Corollary 11.1 (p. 749) with the example $G_4(n,r)$ and the attribution of the question to Erdős (p. 741), read on the page images, paged on corollary_11_1, and Theorem 11 (pp. 747--748), of which it is the case $k=0$, paged on theorem_11. The paper's main directed result, Theorem 2D (p. 751), is paged on theorem_2d at statement depth. The lemmas behind Theorem 11 (pp. 745--747) are recorded as statements read on the page images with their proofs followed at the depth the read status states. Theorems 1--10 and the rest of the directed § 6, which no problem page consumes, are recorded from the page images or the text layer as the read status says. Nothing here is independently reviewed.

Bears on. #1012: Corollary 11.1 (printed p. 749, PDF p. 11) is the theorem the site credits to the paper, read here in the original: a graph on $n\ge2r+3$ vertices with at least $\binom{n-r-1}2+\binom{r+2}2+1$ edges contains a circuit of every length $d$ with $3\le d\le n-r$, and a graph on $r+3\le n<2r+3$ vertices with at least $[\frac14n^2]+1$ edges does too. With $r=k$ the first bound is the problem's edge count, the range is the site's $n\ge2k+3$, and the length $n-k$ is included, so $f(k)\le2k+3$ in the site's letters; the statement matches Theorem 8 of Li and Ning 2023 (p. 4), through which the problem page had read it. The paper itself frames the corollary as the answer to Erdős's 1969 question (p. 741, citing Problem 4 of the Oxford list, paged at Erdős 1971, item 4; p. 749), with the problem's edge count and not the misprinted count of the list, and its $G_4(n,r)$ (p. 741) is the problem's sharpness graph with the paper's own statement that it has no circuit of length $n-r$ or more; it credits the case $r=1$ to Bondy 1971, Theorem 2 and the case $r=0$ to Ore 1961, Theorem 4.3. Corollary 11.1 is the case $k=0$ of Theorem 11 (pp. 747--748), whose cases with a positive minimum valency the problem does not use. The second bound bears on the smallest admissible $f(k)$, which the problem page had left open: for $k+3\le n\le2k+2$ the problem's count is at least $[\frac14n^2]+1$ (an elementary comparison recorded on the result page), so the corollary's two bounds together give the problem's implication for every $n\ge k+3$. The problem page reads the corollary and Theorem 11 on the page images at statement depth with the proof of Theorem 11 followed; nothing is independently reviewed.

Results.

• Corollary 11.1 (p. 749): on $n\ge r+3$ vertices, $\binom{n-r-1}2+\binom{r+2}2+1$ edges when $n\ge2r+3$, or $[\frac14n^2]+1$ edges when $n<2r+3$, force a circuit of every length from $3$ to $n-r$; the first bound is least possible by $G_4(n,r)$; the case $k=0$ of Theorem 11.
• Theorem 11 (pp. 747--748): the seven-case edge bound that, with minimum valency $k$ on $n\ge r+3$ vertices, forces a circuit of every length from $3$ to $n-r$, each bound least possible; proved on pp. 748--749 from Corollaries 8.2, 9.1 and 9.2, Theorems 1 and 10 and Lemmas 11.1 and 11.2.
• Theorem 2D (p. 751): the directed form of Ore's theorem, the main directed result, proved on pp. 751--754 through Lemmas 2D.1--2D.3 and Theorem 6D.
• Theorem 6 (p. 742, not paged): the paper's own undirected result on valency sums of nonadjacent pairs, a corollary of the directed Theorem 6D (p. 750).

No file of this source is held: no license on record permits its redistribution, and the card cites the edition it names above.