REVIEW 4 major objections 4 minor 9 references
The minimum size of a $k$-connected locally nonforesty graph
T0 review · 4 major / 4 minor · reviewed 2026-08-10 · deepseek-v4-flash
Pith's one-line read For k-connected locally nonforesty graphs, the exact minimum number of edges is now known for every k.
desk verdict Solves k=1, 2, 4 with real case analysis and clean block decomposition, but the claimed general-k determination rests on an unstated k=5 construction and one omitted subcase. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The local subgraph $L(v)=G[N(v)]$, together with the observation that a graph is locally nonforesty exactly when every vertex is the hub of a wheel. Three counting regimes carry the argument: for $4$-connected graphs, the $4$-regular extremal case forces $L(v)=C_3+K_1$ and leads to disjoint $K_4$s; for $2$-connected graphs, the proof separates the degree-$3$ vertices $S$, counts edges through $N(S)$, and optimizes a maximum of two linear functions in $s=|S|$; for connected graphs, the proof passes to the block-cutpoint tree and shows all nontrivial blocks are 2-connected locally nonforesty blocks of order at most $6$.
What would settle it
Find, by computation or construction, a 5-connected locally nonforesty graph on 9 vertices with 23 edges, or show that none exists. The k=5 formula holds only if such graphs exist for every n, and the paper's only support for this is an unprinted 'tedious' construction.
Extended reading notes
Core claim
The paper determines the function $f(k,n)$, the minimum size of a $k$-connected locally nonforesty graph of order $n$. For $k\ge 5$, $f(k,n)=\lceil kn/2\rceil$, meaning the local-cycle condition has no effect on the extremal value. For $k=4$, $f(4,n)=2n$ when $n\equiv 0\pmod 4$ and $2n+1$ otherwise. For $k=2$, $f(2,n)=2n-\lfloor n/4\rfloor$ when $n\equiv 0,3\pmod 4$ and $2n+1-\lfloor n/4\rfloor$ otherwise. For $k=1$, $f(1,n)=2n-1-\lfloor n/4\rfloor$ when $n\equiv 0,3\pmod 4$ and $2n-\lfloor n/4\rfloor$ otherwise. Each lower bound is proved by degree and cut arguments, and each is matched by explicit constructions built from rings of $K_4$ blocks with one modified block depending on $n\bmod 4$. The connected case uses block-cutpoint decomposition and reduces to 2-connected locally nonforesty blocks of order at most $6$.
Load-bearing premise
The k=5 formula assumes that, for every n, a 5-connected locally nonforesty graph with exactly ceil(5n/2) edges exists; the paper states this with no construction or verification.
Editorial extensions
If this is right
- The locally nonforesty condition does not change the extremal size once $k$ reaches $5$: for $k\ge 6$ the Harary graphs are already extremal, and the paper asserts the same for $k=5$.
- Every extremal $4$-connected graph on a multiple of $4$ vertices must be $4$-regular with every neighborhood isomorphic to $C_3+K_1$; for other orders exactly one extra edge is needed and enough.
- For $2$- and $1$-connected graphs the extremal edge count is close to $7n/4$, with the residue class of $n$ modulo $4$ deciding whether the floor term is subtracted from $2n$ or from $2n+1$.
- The connected case reduces structurally to blocks: nontrivial blocks are locally nonforesty 2-connected blocks of order at most $6$, so the extremal connected graph is a tree-like arrangement of small dense blocks.
Reading between the lines
- The missing $k=5$ construction is the one spot where a reader cannot yet check the theorem for themselves; an explicit enumeration of such graphs for small $n$ would either close the gap or expose a counterexample.
- The block argument for $k=1$ suggests a general transfer principle: once an extremal family of 2-connected locally nonforesty graphs is known, attaching such blocks by bridges gives a connected extremal family with almost the same edge count. The paper demonstrates this for the present family, though it does not state the principle abstractly.
- A natural analogue is to require every local subgraph to contain a cycle of length at least $t$; the floor-term corrections in $n\bmod 4$ suggest similar periodic corrections modulo $t$ would appear for such variants.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper studies the extremal function f(k,n), the minimum number of edges in a k-connected graph on n vertices in which every local subgraph contains a cycle. The authors state that for k≥5 this minimum is ceil(kn/2), and then prove exact formulas for k=4, k=2, and k=1, all for n≥8. The k=4 lower bound is proved by showing that a 4-regular locally nonforesty graph must have order divisible by 4; the k=2 lower bound is a degree-sequence and case analysis; the k=1 result is obtained from the k=2 result through a block decomposition. Explicit constructions are provided for each residue class via figures. The k=3 case is cited to a previous paper by the same authors.
Significance. If the gaps identified below are filled, the paper gives a complete solution to a natural extremal problem and extends the authors' earlier k=3 result to all k. The lower-bound arguments for k=2 and k=4 are concrete and largely checkable, and the block-decomposition approach for k=1 is coherent. The paper contains no fitted parameters and no circular use of its own conclusions; the cited k=3 result is an independent prior theorem. The claimed dichotomy—that the locally nonforesty condition has no effect on the minimum size for k≥5—would be a clean and publishable statement, but it currently rests on an unverified construction.
major comments (4)
- [Section 1] The determination of f(k,n) for k≥5 is load-bearing for the title and abstract, but the k=5 upper bound is only asserted: the sentence 'For k=5 we have constructed 5-connected locally nonforesty graphs of order n and the size ceil(kn/2), but it is tedious to describe those graphs and verify their properties' supplies no construction, figure, or verification. This is not a routine appeal to Harary graphs: the standard Harary graph H_{5,n} is not locally nonforesty for even n, since for n≥8 the neighborhood of a vertex induces a subgraph isomorphic to P4∪K1, which is a forest. The assertion is therefore a substantive existence claim for every n, and the stated formula f(k,n)=ceil(kn/2) for k=5 is unproved as written. Please supply the construction (or a precise citation) and verify 5-connectivity and local nonforesty for all residue classes, or restrict the claim to k≥6.
- [Section 3, Subcase 2.3(a)] In the proof of Theorem 3 for n=4k+2, the exclusion of the case e(G)=7k+4 with s=2k is omitted. The text says 'The proof in this case is similar to the one in Subcase 2.2, and we omit the details.' This is one of the four residue cases needed for the lower bound of the k=2 formula, so the proof of Theorem 3 is incomplete as written. Please include the details or give a formal reduction to Subcase 2.2.
- [Section 4, after Claim 2] The edge bounds for small 2-connected locally nonforesty blocks are asserted without proof: 'It is not difficult to check that e(Mi)=6 if mi=4, e(Mi)≥9 if mi=5, e(Mi)≥11 if mi=6 and e(Mi)≥13 if mi=7.' These bounds are used in Claim 3 to justify the replacements by D2 and by Gn−z1y2, and they are therefore load-bearing for Theorem 4. Since the proof of Claim 3 also relies on the unstated edge count of D2, please provide a short lemma covering the four small orders and the edge count of D2.
- [Section 4, Claim 4] The proof of Claim 4 (t5+t6≤1) only treats the case t5≥2 and says 'Other cases are similar.' The remaining cases—t6≥2 and t5=t6=1—are needed to conclude the claim, which is then used in the final counting for Theorem 4. Please supply the missing cases or a uniform argument.
minor comments (4)
- [Abstract and Theorems 2–4] The abstract states the result for order n without qualification, while the theorems are stated only for n≥8. Please state the range explicitly in the abstract or add a remark on the small values of n.
- [Throughout] There are several typographical errors: 'neig hborhood' in the abstract, 'forst' for 'forest' in Section 4, and 'a contradicting our assumption' in Subcase 2.3(b). These should be corrected.
- [Section 4, Claim 2] In the isolated-vertex case, the equality N_G(x)∩N_G(v)=∅ is asserted without explanation. It follows because M1 is a block, so a common neighbor of x and v outside M1 would create a larger 2-connected subgraph; this justification should be stated explicitly.
- [Section 2, Theorem 2] In the case L(v)=K4, the statement 'since G is 4-regular, then G=K5' should mention that G is connected, so the K5 component is the whole graph; otherwise the sentence is slightly ambiguous.
Circularity Check
No circular derivation: the bounds are proved directly and the only self-citation is an independent prior k=3 theorem; the k=5 construction is asserted without proof, which is a completeness gap, not circularity.
full rationale
The paper has no fitted parameters and never feeds the claimed f(k,n) formula back into any hypothesis. The lower bounds in Theorems 2–4 are proved directly from κ(G)≥k and the local-nonforesty condition, and the upper bounds are explicit constructions using the graphs in Figures 1–2. Theorem 4 uses Theorem 3, which is proved earlier in the paper; this is a forward dependency, not circularity. The only self-citation is [6], the authors' earlier determination of the 3-connected case. That citation is load-bearing for the k=3 component of the general-k statement, but it is a prior theorem with independent content, not an assumption equivalent to the paper's target, so it does not make the derivation circular. Section 1 also asserts, without proof, that 5-connected locally nonforesty graphs of order n and size ceil(5n/2) have been “constructed”, saying “it is tedious to describe those graphs and verify their properties.” This is a genuine completeness gap: the k=5 upper bound is not demonstrated in the paper and no construction, figure, or reference is supplied. It is an omission, not a circular step, because nothing is defined in terms of the desired minimum value. Thus no step in the derivation reduces to its own input by construction.
Assumptions & free parameters
assumptions (5)
- domain assumption All graphs are finite and simple
- standard math Harary graphs H_{k,n} are k-connected and have exactly ceil(kn/2) edges
- standard math Block-cutpoint graph facts and block definitions
- ad hoc to paper Small 2-connected locally nonforesty blocks have edge counts at least 6, 9, 11 and 13 for orders 4, 5, 6 and 7 respectively
- ad hoc to paper 5-connected locally nonforesty graphs of order n and size ceil(5n/2) exist for all n
Cite this review
Pith. "Pith review of The minimum size of a $k$-connected locally nonforesty graph." pith.science (2026). https://pith.science/paper/UUC5VHJE
@misc{pith2026250113980,
author = {Pith},
title = {Pith review of: The minimum size of a $k$-connected locally nonforesty graph},
year = {2026},
howpublished = {\url{https://pith.science/paper/UUC5VHJE}},
note = {Machine review of arXiv:2501.13980}
}
abstract
A local subgraph of a graph is the subgraph induced by the neighborhood of a vertex. Thus a graph of order $n$ has $n$ local subgraphs. A graph $G$ is called locally nonforesty if every local subgraph of $G$ contains a cycle. Clearly, a graph is locally nonforesty if and only if every vertex of the graph is the hub of a wheel. We determine the minimum size of a $k$-connected locally nonforesty graph of order $n.$
Figures
Reference graph
Works this paper leans on
-
[6]
C. Li, Y. Tang and X. Zhan, The minimum size of a 3-connected locally nonforesty graph, arXiv:2410.23702, 31 October 2024
work page Pith review arXiv 2024
-
[1]
Asratian, Every 3-connected, locally connected, claw-fre e graph is Hamilton- connected, J
A.S. Asratian, Every 3-connected, locally connected, claw-fre e graph is Hamilton- connected, J. Graph Theory, 23(1996), no.2, 191-201
work page 1996
- [2]
-
[3]
G. Chartrand, R.J. Gould and A.D. Polimeni, A note on locally connect ed and Hamiltonian-connected graphs, Israel J. Math., 33(1979), no.1, 5-8
work page 1979
-
[4]
V. Chernyshev, J. Rauch and D. Rautenbach, Forest cuts in sp arse graphs, arXiv: 2409.17724, 26 September 2024
arXiv 2024
-
[5]
J. Davies and C. Thomassen, Locally Hamiltonian graphs and minimal size of max- imal graphs on a surface, Electron. J. Combin., 27(2020), no.2, Pa per No. 2.25
work page 2020
-
[7]
D.J. Oberly and D.P. Sumner, Every connected, locally connected nontrivial graph with no induced claw is Hamiltonian, J. Graph Theory, 3(1979), no.4, 3 51-356
work page 1979
-
[8]
West, Research problems, Discrete Math., 272(2003), 301 -306
D.B. West, Research problems, Discrete Math., 272(2003), 301 -306
work page 2003
Show all 9 references
-
[9]
West, Introduction to Graph Theory, Prentice Hall, Inc., 19 96
D.B. West, Introduction to Graph Theory, Prentice Hall, Inc., 19 96. 12
Reviewed August 10, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.