{"id":"ce786a56-c4d2-4162-b02f-d7063920ef2b","arxiv_id":"2501.13980","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"The minimum size of a k-connected locally nonforesty graph of order n is determined exactly for k=4, k=2 and k=1, and equals ceil(kn/2) for k at least 5.","lead":"This paper determines, for every connectivity level k, the smallest number of edges a k-connected graph can have when the neighborhood of every vertex contains a cycle. It gives exact formulas for k=4, k=2 and k=1, and shows the answer is the trivial degree bound for k at least 5.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The general-k theorem depends on an unstated k=5 construction: Section 1 asserts existence of 5-connected locally nonforesty graphs of size ceil(5n/2) without supplying them. If Harary H_{5,n} works, the gap is easily closed, but as written the claim is unsupported.","rationale":"The reader identified the unsupported k=5 existence assertion as the weakest assumption, and I agree: it is the only place where the claimed general-k theorem relies on an unstated construction rather than a proof or a standard citation. The concern is concrete and load-bearing because the upper bound in the 'trivial' regime k>=5 must be witnessed by actual graphs; for k>=6 the paper names Harary's graphs, while for k=5 it merely promises a tedious family. I found no internal inconsistency that would make the theorem false, and the nearby statements for k=4, k=2, and k=1 appear internally coherent, modulo the usually minor 'similar/omitted' proof fragments flagged by the reader. My proposed test is deliberately cheap: if the standard Harary graph H_{5,n} is indeed 5-connected and locally nonforesty, then the k=5 gap is closed by a known construction and the paper's claim is correct; otherwise the missing family is an essential defect. Since the concern matches the reader's and does not by itself disprove the theorem, keeping the conditional verdict is the right call.","tokens_in":8920,"tokens_out":18037,"duration_ms":179184,"concrete_test":"Implement or draw the standard Harary graph H_{5,n} for n=6..20 (both parities), verify it is 5-connected and has ceil(5n/2) edges, and check that every vertex's neighborhood contains a cycle. If all pass, replace the 'tedious' sentence by a citation to Harary's construction; if some n fails, exhibit the promised k=5 family for that n.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Section 1 reduces the whole k-general result to three ingredients: the proved cases k=1,2,4 (Theorems 2-4), the cited 3-connected case [6], and the assertion that for k>=5 the minimum is ceil(kn/2). The lower bound is immediate from delta>=k. The upper bound is supplied for k>=6 by Harary's graphs, but for k=5 the paper only says '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.' No construction, figure, or verification is given. Since the abstract claims a general-k determination, this one sentence is load-bearing: if no such graphs exist for some residue class of n, the headline formula fails exactly in the 'trivial' regime. The omission is conspicuous because the standard Harary graph H_{5,n} is 5-connected, has ceil(5n/2) edges, and appears likely to be locally nonforesty; if so, the gap is purely expository and closable by one reference. The same section also leaves the k=3 case to [6], but that is an explicit citation rather than an unstated construction.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":9202,"tokens_out":17861,"duration_ms":177447,"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":[{"comment":"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":"Section 1"},{"comment":"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":"Section 3, Subcase 2.3(a)"},{"comment":"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":"Section 4, after Claim 2"},{"comment":"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.","section":"Section 4, Claim 4"}],"minor_comments":[{"comment":"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.","section":"Abstract and Theorems 2–4"},{"comment":"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":"Throughout"},{"comment":"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":"Section 4, Claim 2"},{"comment":"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.","section":"Section 2, Theorem 2"}],"recommendation":"major_revision","confidential_remarks":"The main risk is the unproved k=5 construction. If the authors cannot supply it, the general-k claim should be weakened to k≠5 or to k≤4 plus k≥6. The remaining gaps—Subcase 2.3(a) and the small-block bounds—are omissions that can likely be repaired with additional case analysis. The paper's core k=2 and k=4 arguments are otherwise plausible, so I do not recommend rejection unless the k=5 assertion turns out to be false."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The headline: the paper determines f(k,n) for k=4, 2, 1 and claims the k>=5 cases are trivial, but the k=5 existence step is asserted rather than shown. The k=4, 2, 1 theorems are real work and check out in outline; the k>=5 claim is load-bearing and unsupported as written.\n\nWhat is new: the exact formulas for 4-connected, 2-connected, and connected locally nonforesty graphs. The reduction is clean: for k>=6 Harary graphs give the upper bound; for k=5 the authors say they have constructed examples but do not describe them. The paper is honest that the k=3 case is in the companion paper [6]. The block decomposition in Section 4 is a solid argument that reduces the connected case to the 2-connected case. There is no circularity and no fitted parameters; the one self-citation is legitimate.\n\nSoft spots, in order of importance. First, the general-k theorem in the abstract depends on the k=5 construction. A single sentence says \"it is tedious to describe those graphs\" and then the paper moves on. If Harary's H_{5,n} works, this is a one-paragraph fix, but as written the claim is not verifiable. The referee should ask for that construction or a reference. Second, Subcase 2.3(a) in Theorem 3 is explicitly omitted (\"similar ... we omit the details\"). The subcase is needed to exclude an equality case for n ≡ 2 mod 4, and the reader is asked to trust that the same argument goes through. Third, the small-block edge bounds in Section 4 (e(Mi)=6 for order 4, etc.) are asserted without derivation; they are plausible and easily checked by hand, but they are still assertions.\n\nOverall the paper is a competent, narrow extremal result. The k=4 and k=1 arguments are the strongest parts; the k=2 case has a real gap in the omitted subcase. The k>=5 claim is, as written, an unsupported assertion, so the \"general k\" statement in the abstract should be softened until the construction appears. This is not a fatal flaw—the main results for k<=4 appear correct and are likely new—but it needs revision.\n\nThe paper is for specialists in graph connectivity and extremal problems. It deserves peer review; a good referee will ask for the k=5 construction and the omitted subcase, and then the paper should be publishable. My recommendation: send it to review, with the caveat that the general-k claim requires the k=5 construction and the missing subcase before acceptance.","headline":"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.","tokens_in":9711,"tokens_out":2285,"would_cite":false,"duration_ms":23334,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C35","05C38","05C40"],"pacs":[],"model":"deepseek-v4-flash","headline":"For k-connected locally nonforesty graphs, the exact minimum number of edges is now known for every k.","keywords":["locally nonforesty graph","local subgraph","k-connected graph","extremal graph theory","minimum size","wheel hub","block decomposition"],"falsifier":"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.","tokens_in":8682,"feed_emoji":"🛞","tokens_out":6648,"duration_ms":66620,"temperature":0.7,"pith_summary":"This paper answers an extremal question: among $k$-connected graphs on $n$ vertices in which every vertex has a cycle among its neighbors, what is the smallest possible number of edges? It gives exact formulas for every $k$. The main structural surprise is a threshold: for $k=5$ and larger the local-cycle condition imposes no extra cost beyond $k$-connectivity, while for $k=1,2,4$ the minima are given by explicit formulas involving $⌊n/4⌋$ and the residue of $n$ modulo $4$. The paper also shows that a conjecture posed in [4] about $3$-connected locally nonforesty graphs is false, since the companion paper [6] had already determined that case.","feed_headline":"Exact edge minima found for all k-connected locally nonforesty graphs","feed_subtitle":"The answer is ceil(kn/2) once k is at least 5; below that, edge counts follow a four-step wobble.","key_machinery":"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$.","core_discovery":"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$.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"The paper that posed the conjecture about 3-connected locally nonforesty graphs, giving the problem its starting point.","marker":"[4]"},{"why":"The authors' preceding paper that solved the k=3 case and showed the conjecture fails, which the present paper extends to general k.","marker":"[6]"},{"why":"The textbook that supplies Harary's graphs for k>=6 and the block-cutpoint decomposition used in the k=1 proof.","marker":"[9]"}],"fun_headline_variants":["Exact edge minima for all k-connected locally nonforesty graphs","For k≥5, local cycles cost nothing in edge minima","Low-connectivity case: four-step wobble in edge counts","Sparsest k-connected graphs with cyclic neighborhoods","All k solved: minimum edges with every vertex a wheel hub"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Exact edge minima for all k-connected locally nonforesty graphs","For k≥5, local cycles cost nothing in edge minima","Low-connectivity case: four-step wobble in edge counts","Sparsest k-connected graphs with cyclic neighborhoods","All k solved: minimum edges with every vertex a wheel hub"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001078,"raw_usage":{"total_tokens":4492,"prompt_tokens":906,"completion_tokens":3586,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":522,"completion_tokens_details":{"reasoning_tokens":3514}},"tokens_in":522,"tokens_out":3586,"duration_ms":28276,"temperature":1.0,"reasoning_tokens":3514,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-10T16:17:34.930799+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":"West, Introduction to Graph Theory, Prentice Hall, Inc., 19 96","cited_arxiv_id":null,"evidence_quote":"The textbook that supplies Harary's graphs for k>=6 and the block-cutpoint decomposition used in the k=1 proof."},{"cited_title":"The minimum size of a $3$-connected locally nonforesty graph","cited_arxiv_id":"2410.23702","evidence_quote":"The authors' preceding paper that solved the k=3 case and showed the conjecture fails, which the present paper extends to general k."}],"review_version":1}