Narins 2017 graphs without proper subgraphs minimum degree

../

lemma_2_1: For an even 1-3 tree T, the graph G(T) obtained by joining two new adjacent vertices to every leaf has a cycle of length 2k + 1 exactly when T has a leaf-to-leaf path of length 2k - 2, with a matching rule for even cycles.

lemma_4_2: Every graph on n >= 2 vertices with at least 2n - 2 edges has an induced subgraph of minimum degree 3, so a degree 3-critical graph is the only such subgraph of itself.

problem_6_1: The paper's Problem 6.1 asks whether some function C(n) tending to infinity makes every degree 3-critical graph on n vertices contain cycles of all even lengths from 4 to 2C(n).

proposition_5_1: Every graph with n >= 6 vertices, 2n - 2 edges and no proper induced subgraph of minimum degree 3 contains a cycle of length 6.

theorem_1_2: There are arbitrarily large graphs with n vertices, 2n − 2 edges and no proper induced subgraph of minimum degree 3 that contain no 23-cycle, disproving the Erdős–Faudree–Gyárfás–Schelp conjecture that all short cycles appear.

theorem_1_3: Every sufficiently large even 1-3 tree has leaf-to-leaf paths of all even lengths from 0 to 18, while some infinite family of even 1-3 trees has no leaf-to-leaf path of length 20.

theorem_1_4: Under the literal, non-induced reading of the 1988 definition the graphs with 2n − 2 edges are wheels or a modified wheel family and contain cycles of every length from 3 to n.

theorem_4_1: A graph on n vertices with 2n − 2 edges has no proper subgraph, induced or not, of minimum degree 3 exactly when it is a wheel or is obtained by identifying the two connectors of a graph H_i with those of a graph H_j.

---

Narins, Lothar and Pokrovskiy, Alexey and Szabó, Tibor, 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; Crossref record read; the site's reference text gives "Combinatorica (2017), 495--519"). Preprint arXiv:1408.5289 (v1, 22 August 2014). The arXiv record names arXiv's non-exclusive distribution license (arXiv:1408.5289), every other right reserved.

Edition read. The copy read for this card is arXiv:1408.5289v1, stamped "[math.CO] 22 Aug 2014" and dated August 25, 2014 on its first page, 22 pages with a complete text layer (the arXiv comment reads "22 pages, 14 figures"); the arXiv record lists this one version and no journal reference. The journal text was not compared; every locator on this card and on the result pages is a preprint page. Result pages: theorem_1_2, theorem_1_3, lemma_2_1, theorem_1_4, theorem_4_1, lemma_4_2, proposition_5_1 and problem_6_1.

Read status: claims checked for the definition of degree $3$-critical graphs and the account of the earlier results (p. 2, text layer), Conjecture 1.1 and the historical remark (pp. 2--3), Theorems 1.2, 1.3 and 1.4 (pp. 3--4, page images), the construction $G(T)$ and Lemma 2.1 (p. 4, page image), Theorem 4.1, Lemma 4.2 and Lemma 4.3 (pp. 15--16, text layer), Proposition 5.1 (p. 19, text layer) and Section 6 (p. 21, text layer); later read on the page images, for the result pages: Lemma 2.2, Definition 2.3 and Theorem 2.5 (pp. 6--7), the proofs of Theorems 1.3(ii) and 1.2 (p. 8), Proposition 3.2 (p. 9), Theorem 3.3 (p. 10), Proposition 3.9 and the proof of Theorem 1.3(i) (p. 14), the definitions of $\mathcal G$, the wheels and $H_n$ (pp. 14--15) and the outline of the proofs of Theorem 4.1 and Proposition 5.1 (pp. 16--20); no proof was checked.

The paper studies degree $3$-critical graphs: graphs on $n$ vertices with $2n-2$ edges having no proper induced subgraph of minimum degree $3$ (the term follows Bollobás and Brightwell, p. 2). Theorem 1.2 disproves the conjecture of Erdős, Faudree, Gyárfás and Schelp that such graphs contain all cycles of lengths $3,4,\ldots,C(n)$ with $C(n)$ tending to infinity, by exhibiting an infinite family of degree $3$-critical graphs with no cycle of length $23$. A historical remark (p. 3) records that the 1988 paper's definition reads "no proper subgraph has minimum degree 3", that its Examples 1, 2, 3, 5 and 6 have proper non-induced subgraphs of minimum degree $3$, and that its results and proofs hold under the induced reading, so that it is "plausible to assume" that the word "induced" belongs in the conjecture. The construction rests on Theorem 1.3, a result of independent interest about leaf-to-leaf path lengths in even $1$-$3$ trees: every sufficiently large such tree has leaf-to-leaf paths of all even lengths up to $18$, but there is an infinite family with no leaf-to-leaf path of length $20$; for a $1$-$3$ tree $T$, $G(T)$, the tree with two adjacent vertices joined to all its leaves, is degree $3$-critical, and for an even one its odd cycles correspond to leaf-to-leaf paths (Lemma 2.1). Theorem 1.4 shows that if "induced" is dropped from the definition, the graphs with $n$ vertices, $2n-2$ edges and no proper subgraph of minimum degree $3$ are pancyclic, from a structure theorem (Theorem 4.1) identifying them as the wheels and one modified wheel family. Section 5 (Proposition 5.1) verifies that every degree $3$-critical graph on at least $6$ vertices contains a $6$-cycle, so the smallest cycle length missing from some infinite family lies between $7$ and $23$; Section 6 notes that the method can forbid any one odd cycle length $m\ge23$ and asks about even cycles (Problem 6.1). For Problem 815 this settles the conjecture in the negative and leaves the even case open.

Source: https://arxiv.org/abs/1408.5289.

Contents

• Conjecture 1.1 (p. 2, Erdős, Faudree, Gyárfás and Schelp): for some increasing function $C(n)$, each degree $3$-critical graph on $n$ vertices has a cycle of every length from $3$ to $C(n)$. The historical remark on the missing word "induced" (p. 3). The earlier results as the paper reports them (p. 2): on $n\ge5$ vertices, cycles of lengths $3$, $4$, $5$ and of length at least $\lfloor\log_2n\rfloor$ but not necessarily more than $\sqrt n$ (Erdős, Faudree, Gyárfás, Schelp); the longest cycle at least $4\log_2n-o(\log n)$ and constructions with none longer than $4\log_2n+O(1)$ (Bollobás and Brightwell, Discrete Math. 75 (1989), 47--53, not held); Erdős's conjecture that $2n-1$ edges force a degree $3$-critical subgraph on at most $(1-\epsilon)n$ vertices (cf. the 1990 paper with Faudree, Rousseau and Schelp).
• Theorem 1.2 (p. 3): some infinite sequence $(G_n)_{n=1}^\infty$ of degree $3$-critical graphs has no member containing a cycle of length $23$.
• Theorem 1.3 (p. 3): (i) there is $N_0$ such that every even $1$-$3$ tree with at least $N_0$ vertices has leaf-to-leaf paths of lengths $0,2,4,\ldots,18$; (ii) some infinite family $(T_n)_{n=1}^\infty$ of even $1$-$3$ trees has no member with a leaf-to-leaf path of length $20$.
• Theorem 1.4 (p. 4): every graph on $n$ vertices with $2n-2$ edges in which no proper subgraph, induced or not, has minimum degree $3$ is pancyclic; from Theorem 4.1 (p. 15), the family consists of all wheels and the graphs formed by identifying the two connectors of a copy of $H_i$ with those of a copy of $H_j$.
• The construction (p. 4): $G(T)$ adds to a tree $T$ two adjacent vertices joined to every leaf; for a $1$-$3$ tree it is degree $3$-critical; Lemma 2.1 (page): for an even $1$-$3$ tree, $G(T)$ has a $C_{2k+1}$ if and only if $T$ has a leaf-to-leaf path of length $2k-2$, and a $C_{2k}$ if and only if $T$ has two vertex-disjoint leaf-to-leaf paths of total length $2k-4$ or one of length $2k-2$.
• Lemma 4.2 (p. 15): a graph with $n\ge2$ vertices and at least $2n-2$ edges has an induced subgraph of minimum degree $3$. Lemma 4.3 (p. 16): an ordering of a degree $3$-critical graph with $d^+(x_1)=3$, $d^+(x_i)=2$ for $2\le i\le n-2$, $d^+(x_{n-1})=1$ and, for $n\ge7$, $d(x_n)\ge4$.
• Proposition 5.1 (p. 19): every degree $3$-critical graph with $n\ge6$ contains a $C_6$.
• Section 6 (p. 21): degree $3$-critical graphs with no $m$-cycle for any odd $m\ge23$; the least missing length lies between $7$ and $23$; Problem 6.1 (cycles of all lengths $4,6,\ldots,2C(n)$?); Conjecture 6.2 (at least $3\log_2n+O(1)$ distinct cycle lengths); Conjectures 6.3--6.4 on leaf-to-leaf path lengths in $1$-$3$ trees. Di Braccio, Katsamaktsis, Ma, Malekshahian and Zhao (Combinatorica 46 (2026), article 11; arXiv:2504.11656) prove Conjecture 6.2 up to a constant factor, prove a corrected form of Conjecture 6.3, disprove Conjecture 6.4 and restate Problem 6.1 as open (their Problem F); their arXiv v2 is held on its own card, the journal text is not.
• References (p. 22): [3] prints the 1988 paper's pages as "25(B):159--201"; the paper's own pagination is 195--201.

Compiled scope

Statements at claims-checked depth on pp. 2--4, 6--7, 9--10, 14--16, 19 and 21; the proofs behind the result pages were followed by their labels on pp. 5--20 and none was checked. Nothing here is independently reviewed. The 1988 paper has its own card, which holds no file of it; Bollobás and Brightwell's paper is not held, and its bounds appear here as this paper states them.

Bears on. #815: Theorem 1.2 gives arbitrarily large degree $3$-critical graphs without $C_{23}$, so the problem's statement fails for $k=23$ under the site's induced definition, and Section 6 (p. 21) says the method gives the same for every odd $k\ge23$; it rests on [extremal_graph_theory/narins_2017_graphs_without_proper_subgraphs_minimum_degree/theorem_1_3|Theorem 1.3] and Lemma 2.1, and Theorem 1.3(i) shows the method cannot omit an odd cycle shorter than $23$. Proposition 5.1 proves the case $k=6$ for $n\ge6$. Theorem 1.4, from Theorem 4.1, shows that under the literal non-induced 1988 wording the graphs are pancyclic; it says nothing about the induced class. Lemma 4.2 describes the class. Problem 6.1 asks for all even lengths up to $2C(n)$, which holds exactly when every fixed even $k$ holds for large $n$ (an equivalence worked out on the Problem 6.1 page, not stated in the paper); the site records the even case as open.

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