{"id":"5db2f2f9-5f5b-4892-a782-93ae992c6547","arxiv_id":"2509.09895","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"For every apex-forest H, every graph with tree-width at least |V(H)|−1 contains H as a minor, and wheels satisfy a new near-linear bound.","lead":"The paper proves that any sufficiently complex network must contain a specific tree-like shape with one extra universal vertex, and gives new bounds for wheel-shaped obstacles. The result sharpens the exact size threshold where the trivial lower bound on tree-width becomes the true answer for a broad family of planar graphs.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Reader's thin-wrist gap is not real; the actual gap is that Lemma 3.4 attaches decompositions of the contracted graph G'_{t,c} without reinserting the contracted paths P_t.","rationale":"The paper's two headline claims are plausible and the wheel proof looks complete, but the apex-forest proof has a presentation gap in the central lemma. I read the octopus definition carefully: the Reader's alleged gap in Theorem 3.5 is resolved by the octopus condition itself, since large bags are leaves with parent size at most |S|, so a thin octopus forces every wrist size below |S|. Thus I cannot agree with that concern. However, the move from G'_{t,c}, a contraction of G_{t,c}, back to G is not justified in Lemma 3.4. This is the most load-bearing point because Theorem 1.1 rests entirely on Lemma 3.4 and Theorem 3.5. The missing argument is likely standard and fixable, so the verdict should remain CONDITIONAL rather than move to REJECT or ACCEPT. There is no issue detected with the wheel section, no circular reasoning, and no data fitting. The authors should either supply the explicit uncontracting step or state that the attached decomposition is of a subgraph of G with the contracted vertices reinserted in a way that preserves the octopus invariants.","tokens_in":16838,"tokens_out":25291,"duration_ms":181583,"concrete_test":"Write out the missing lift in Lemma 3.4: from the thin (X_t, |V(F)|)-octopus of G'_{t,c}, build a thin (X_t, |V(F)|)-octopus of G_{t,c} by expanding each x in X_t back into P_t and reinserting S, e.g. attaching path-decompositions of the P_t and a bag for G[S] as children of the root. Verify (i) every bag of size at least |V(F)|+1 is a non-root leaf with parent of size at most |X_t|, (ii) every vertex and edge of G_{t,c} is covered, and (iii) the intersection with the rest of T^3 is exactly X_t. Test with F a long path, |S| = 1, and P_t of length greater than one. If such a lift fails, Lemma 3.4 is false as written; if it succeeds, inserting this paragraph repairs the proof.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The Reader's stated gap in Theorem 3.5 is not a gap: in an (S,w)-octopus, any child c with |X_c| >= w+1 is a non-root leaf whose parent p satisfies |X_p| <= |S|. Hence a thin octopus (no wrist with |X_t| = |S|) automatically has every wrist of size < |S|, so with |S| = 1 the conclusion |X_t| = 0 is valid. The actual load-bearing gap is in Lemma 3.4. For each thick wrist t and child c in Q_t, G'_{t,c} is obtained from the subgraph G_{t,c} of G by contracting the paths P_t into X_t. Induction gives a thin (X_t, |V(F)|)-octopus of the contracted graph G'_{t,c}. The proof then says to attach (T_{t,c}, X_{t,c}) to T^3 along X_t and obtains a tree-decomposition of G. But V(G'_{t,c}) is generally smaller than V(G_{t,c}): all vertices of S and all internal vertices of the paths P_t have been identified with X_t, so they occur in no bag of T_{t,c}. The attach operation of Section 2 requires V(G) ∩ V(G_i) to be a single bag, and does not explain how to reinsert these vertices. In particular, if an internal vertex of some P_t belongs only to a deleted bag X_c, then it is absent from every bag of (T^*, X^*), so (T^*, X^*) is not shown to be a tree-decomposition of G. A lifting/uncontracting argument is needed and is not supplied; it is also not obvious that such a lift preserves the octopus bound, since reinserting a long path into bags can create large internal bags.","agreement_with_reader":"disagree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies the function f(H), the smallest integer such that every graph of tree-width at least f(H) contains the planar graph H as a minor, for two families of planar graphs with no two disjoint cycles. Theorem 1.1 asserts that f(H)=|V(H)|-1 for every apex-forest H, improving a bound of Leaf and Seymour and extending the known cases of forests and cycles. Theorem 1.2 asserts that for every wheel H, f(H) is at most max(3/2 |V(H)| - 9/2, |V(H)|-1), with equality when |V(H)| is at most 7. The proofs introduce rooted tree-decompositions called octopuses, which are used in an induction for apex-forests, and a separate induction for wheels. The wheel proof appears to be a complete structural induction, while the apex-forest proof has a significant missing step in the central lemma.","tokens_in":17141,"tokens_out":23777,"duration_ms":214945,"significance":"If the results are correct, they constitute a genuine advance: Theorem 1.1 is sharp for a broad class not previously known to satisfy the trivial lower bound, and the wheel bound improves substantially on earlier polynomial bounds. The octopus machinery is an interesting proof tool, and the explicit conjectures connecting these bounds to Lovász's characterization are useful for future work. The proofs rely on standard tools (Menger's theorem, tree-decomposition connectivity) rather than on unproved assumptions. However, the central apex-forest proof has a load-bearing gap in Lemma 3.4, so Theorem 1.1 is not established as written; the wheel part does not appear to have a comparable problem.","major_comments":[{"comment":"The induction hypothesis is applied to G'_{t,c}, the graph obtained from G_{t,c} by contracting each path in P_t into its endpoint in X^3_t. The resulting tree-decomposition (T_{t,c}, X_{t,c}) is therefore a decomposition of G'_{t,c}, not of G_{t,c}. Its bags contain no internal vertices of the paths P_t and no vertices of S that have been identified with X^3_t. The attaching operation defined in Section 2 requires each attached decomposition to be a decomposition of a graph whose vertex set meets the remaining graph in a single bag. Since V(G'_{t,c}) is a quotient of V(G_{t,c}) rather than a subset of V(G), attaching (T_{t,c}, X_{t,c}) to (T^3, X^3) along X^3_t does not yield a tree-decomposition of G. In particular, if a vertex of G lies on one of the contracted paths P_t and occurs only in a deleted bag X^3_c, it is absent from every bag of (T^*, X^*), so (T^*, X^*) is not shown to cover that vertex or the edges incident with it. A lifting, i.e. uncontracting, argument is needed that reinserts the vertices of P_t into bags while keeping the root bag exactly X^3_t and preserving the property of being a thin (X^3_t, |V(F)|)-octopus. Such an argument is not supplied, and it is not routine because replacing a contracted vertex by a path inside bags can create new bags larger than |V(F)|, potentially violating the octopus condition. This gap is load-bearing: without it, Lemma 3.4 does not imply Theorem 3.5 or Theorem 1.1.","section":"Section 3, Lemma 3.4 (final attachment step)"}],"minor_comments":[{"comment":"In the equality case of Claim 3.4.1, the sentence claiming that restricting (T^3, X^3) to the two nodes t and c yields a non-trivial (S, |V(F)|)-octopus of G is not justified and appears false in general, since edges between S \\ X^3_c and V(G) - S need not be covered by the two bags. The subsequent argument using the vertex u and the fact that all other bags are contained in S proves the required conclusion directly; the restriction sentence and the appeal to minimality of |V(T^3)| should be removed or replaced by this direct argument.","section":"Section 3, Claim 3.4.1"},{"comment":"The final step of Theorem 3.5 is correct, but it is worth spelling out explicitly: if c is a child of a wrist t and |X_c| is at least |V(F)|+1, then the octopus condition directly gives |X_t| ≤ |S| = 1, and thinness excludes equality, so |X_t| = 0. A reader could otherwise think that thinness alone does not exclude wrist bags larger than |S|.","section":"Section 3, Theorem 3.5"},{"comment":"The paper states several times that graphs in the sets F(H) from the literature have tree-width at most |V(H)|-2 but omits proofs of these claims. This is acceptable for context, but the omission should be stated more prominently so that readers do not confuse these auxiliary claims with the main theorems.","section":"Section 1 and Section 3"}],"recommendation":"major_revision","confidential_remarks":"The referee's earlier concern about the thin-wrist argument in Theorem 3.5 is not a real gap; the definition of an (S,w)-octopus already bounds the parent bag of any large bag by |S|, so thinness excludes equality and the final contradiction is valid. The genuine problem is the uncontracting gap in Lemma 3.4. The wheel proof appears complete, so I recommend that the revision focus on repairing the lift argument in Lemma 3.4; if such a lift can be supplied, the paper would be a strong contribution."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The apex-forest theorem is a real step forward, not just an incremental tweak. It generalizes the known tree and cycle cases to all apex-forests, hits the trivial lower bound, and improves the Leaf–Seymour constant. The wheel bound is also a solid improvement over previous results, and the small-wheel exact values are a nice bonus. I found no circularity and no signs of cooked evidence; the proofs are long but follow the established octopus/tree-decomposition toolkit. The wheel section in particular reads carefully and I could not find a hole in it.\n\nThe soft spot is in Lemma 3.4, and it is not the one the reader flagged. The reader's concern about thin wrists is actually a non-issue: in an (S,w)-octopus, if a node t is a wrist, then it has a child c with |X_c| >= w+1, so by the defining property of an octopus the parent bag satisfies |X_t| <= |S|. Thin just forbids equality, so thin really does give |X_t| < |S| for every wrist. That part of Theorem 3.5 is fine.\n\nThe real problem is the attach step in Lemma 3.4. The proof takes a thin (X_t, |V(F)|)-octopus of the contracted graph G'_{t,c}, whose vertex set is essentially X_t ∪ X_c because the paths P_t and the set S have been contracted into X_t. It then tries to attach those decompositions to a tree-decomposition of the original graph G. But the attach operation defined in Section 2 requires V(G) ∩ V(G_i) to be a bag of both decompositions; here G'_{t,c} is not a subgraph of G, and all the internal vertices of the paths P_t (and the vertices of S) are missing from the bags of T_{t,c}. To get a true tree-decomposition of G you need to uncontract the paths, replacing each vertex of X_t in the bags by the whole path. That lifting step is not written down, and it is not obvious that it preserves the octopus bounds: a bag that contains several vertices of X_t could balloon in size once the full paths are reinserted. The sentence \"It is easy to see\" hides exactly this difficulty. I would not be surprised if the argument can be repaired, but as written the proof of Lemma 3.4 does not go through.\n\nWho is this for? Graph minors people and anyone working on Seymour's question or degeneracy of H-minor-free graphs. The paper deserves a serious referee, and I would send it to review, but I would make the authors state the lifting argument explicitly or replace it with a different induction. The reader's verdict of CONDITIONAL is about right, just for the wrong reason.","headline":"Genuinely new results worth refereeing, but Lemma 3.4 has a real contraction/lifting gap that the authors need to fix; the reader's own thin-wrist concern is not valid.","tokens_in":17743,"tokens_out":4280,"would_cite":false,"duration_ms":293692,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C83","05C75"],"pacs":[],"model":"deepseek-v4-flash","headline":"Every apex-forest H is forced as a minor once tree-width reaches |V(H)|-1, and wheels obey a near-linear bound.","keywords":["tree-width","graph minors","apex-forest","wheel graph","Grid Minor Theorem","tree-decomposition","thin octopus","minor-free graphs"],"falsifier":"Run the construction of Lemma 3.4 on graphs satisfying its hypotheses and check whether the minimal nontrivial $(S,|V(F)|)$-octopus can have a wrist bag larger than $S$; if it can, the contradiction in Theorem 3.5 fails as written. A decisive counterexample to the theorem would be any graph with tree-width $|V(H)|-1$ that excludes an apex-forest $H$ as a minor.","tokens_in":16572,"feed_emoji":"🌲","tokens_out":13779,"duration_ms":110822,"temperature":0.7,"pith_summary":"The paper studies the smallest tree-width f(H) that forces a planar graph H to appear as a minor. It proves that for every apex-forest H, a graph that becomes a forest after deleting one vertex, this threshold is exactly |V(H)|-1, the smallest value it can possibly have. That means the complete graph on |V(H)|-1 vertices is the only obstruction: no graph with tree-width below the threshold contains H, and every graph at the threshold does. The paper also proves a near-linear upper bound for wheels, f(H) ≤ max(3/2|V(H)|-9/2, |V(H)|-1), with sharp equality when |V(H)|≤7. These results extend the known sharp cases for trees and cycles and improve the previous bounds for both families.","feed_headline":"Exact tree-width threshold found for apex-forest minors","feed_subtitle":"Every graph whose tree-width is one less than the size of H must contain H as a minor; wheels get a near-linear bound.","key_machinery":"The machinery for the apex-forest theorem is the $(S,w)$-octopus: an $S$-rooted tree-decomposition in which every bag of size at least $w+1$ is a non-root leaf whose parent bag has size at most $|S|$. A wrist is a node with a child bag of size at least $w+1$, and the octopus is thin when no wrist has bag size equal to $|S|$; the induction in Lemma 3.4 is designed to produce a thin $(S,|V(F)|)$-octopus whenever $G[S]$ contains a spanning subgraph isomorphic to a subtree of $F$. The wheel theorem uses a different mechanism: it isolates a largest component $M$ of $G-(V(C)\\cup V(P'))$, forms the reduced graph $G^*=G[V(C)\\cup A]$ with $A$ the attachment vertices on the path $P'$, and builds a four-bag path-decomposition of $G^*$ whose largest bag has size at most $\\max\\{\\frac32 k-3,k\\}$.","core_discovery":"The central claim is that the trivial lower bound f(H) ≥ |V(H)|-1 is attained for every apex-forest H. The proof works by assuming a graph G excludes $F^+$ as a minor, where $F$ is a tree and $F^+$ adds one vertex adjacent to every vertex of $F$, and then constructs a rooted tree-decomposition of G in which every bag has size at most |V(F)|. The construction is inductive and maintains a thin octopus: a rooted decomposition where large bags are confined to leaves whose parent bags are small. At the end the octopus has no wrists at all, which forces the decomposition width below |V(F)|. For wheels, the paper shows the threshold is at most max(3/2|V(H)|-9/2, |V(H)|-1) by reducing to a small graph built from the rim cycle, a path, and a largest component, and then exhibiting a four-bag path-decomposition of that reduced graph with controlled bag sizes.","pith_inferences":["An algorithmic consequence the authors leave implicit is that apex-forest-minor-free graphs admit a simple greedy coloring with $|V(H)|-1$ colors in linear time, because the degeneracy bound follows directly from the theorem.","The $3/2$ coefficient in the wheel theorem appears to be an artifact of the four-bag path-decomposition of the reduced graph $G^*$, not of any known lower bound; constructing a longer path-decomposition might yield $f(W_k)=k-1$ for all $k$, which the paper's small-wheel equality supports.","A direct next test is whether the wheel theorem's path-decomposition survives subdividing rim edges; that would address the paper's first structural question for wheels, which is one of the main missing cases between the apex-forest and wheel results."],"forward_implications":["Every apex-forest-minor-free graph is $(|V(H)|-2)$-degenerate, so it can be colored with $|V(H)|-1$ colors.","The apex-forest case adds infinitely many planar graphs $H$ for which the trivial lower bound $f(H) \\ge |V(H)|-1$ is tight, joining trees, cycles, and the small exceptional graphs already known.","For every wheel $H$, every graph with tree-width at least $\\max\\{\\frac32|V(H)|-\\frac92, |V(H)|-1\\}$ contains $H$ as a minor, and for $|V(H)|\\le 7$ the threshold is exactly $|V(H)|-1$.","Combined with the classification of graphs with no two disjoint cycles, positive answers to the paper's three structural questions and an improvement of the wheel bound to $|V(H)|-1$ would imply $f(H)=|V(H)|-1$ for every planar graph with no two disjoint cycles."],"supporting_citations":[{"why":"Establishes the Grid Minor Theorem that guarantees such a threshold f(H) exists for every planar H.","marker":"[26]"},{"why":"Supplies the previous upper bound for apex-forests that Theorem 1.1 improves.","marker":"[20]"},{"why":"Provides the known result f(H)=|V(H)|-1 for forests, which Theorem 1.1 extends.","marker":"[2]"},{"why":"Provides the known result f(H)=|V(H)|-1 for cycles, also generalized by Theorem 1.1.","marker":"[3]"},{"why":"Gives the earlier wheel bound 36|V(H)|-38 that Theorem 1.2 improves.","marker":"[24]"},{"why":"Gives the more recent wheel bound and disjoint-union-cycle bounds that Theorem 1.2 improves.","marker":"[17]"},{"why":"Classifies graphs with no two disjoint cycles, identifying apex-forests and wheels as the motivating cases.","marker":"[22]"},{"why":"Provides the expander-based lower bound, which motivates restricting attention to planar H with few disjoint cycles.","marker":"[25]"}],"fun_headline_variants":["Apex-forests hit trivial tree-width bound","Exact tree-width threshold for apex-forest minors","Wheel minors: tree-width bound at most 1.5|V|-4.5","Tree-width exact for apex-forests, improved for wheels"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that the thin octopus built in Lemma 3.4 has no wrist whose bag is larger than the root bag $S$; the lemma as written only rules out wrist bags of size exactly $|S|$, so if a larger wrist bag can occur, the final step of Theorem 3.5 does not follow.","fun_headline_variants_meta":{"raw":{"variants":["Apex-forests hit trivial tree-width bound","Exact tree-width threshold for apex-forest minors","Wheel minors: tree-width bound at most 1.5|V|-4.5","Tree-width exact for apex-forests, improved for wheels"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000451,"raw_usage":{"total_tokens":2258,"prompt_tokens":920,"completion_tokens":1338,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":536,"completion_tokens_details":{"reasoning_tokens":1264}},"tokens_in":536,"tokens_out":1338,"duration_ms":8414,"temperature":1.0,"reasoning_tokens":1264,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T15:59:23.849223+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run the construction of Lemma 3.4 on graphs satisfying its hypotheses and check whether the minimal nontrivial $(S,|V(F)|)$-octopus can have a wrist bag larger than $S$; if it can, the contradiction in Theorem 3.5 fails as written. A decisive counterexample to the theorem would be any graph with tree-width $|V(H)|-1$ that excludes an apex-forest $H$ as a minor.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Establishes the Grid Minor Theorem that guarantees such a threshold f(H) exists for every planar H."},{"cited_title":"Tree-width and planar minors.Journal of Combinatorial Theory, Series B, 111:38–53, 2015","cited_arxiv_id":null,"evidence_quote":"Supplies the previous upper bound for apex-forests that Theorem 1.1 improves."},{"cited_title":"Seymour, and Robin Thomas","cited_arxiv_id":null,"evidence_quote":"Provides the known result f(H)=|V(H)|-1 for forests, which Theorem 1.1 extends."},{"cited_title":"Tree-width and circumference of graphs.Journal of Graph theory, 43(1):24–25, 2003","cited_arxiv_id":null,"evidence_quote":"Provides the known result f(H)=|V(H)|-1 for cycles, also generalized by Theorem 1.1."},{"cited_title":"Thilikos","cited_arxiv_id":null,"evidence_quote":"Gives the earlier wheel bound 36|V(H)|-38 that Theorem 1.2 improves."},{"cited_title":"Pascal Gollin, Kevin Hendrey, Sang-il Oum, and Bruce Reed","cited_arxiv_id":null,"evidence_quote":"Gives the more recent wheel bound and disjoint-union-cycle bounds that Theorem 1.2 improves."},{"cited_title":"On graphs not containing independent circuits.Matematikai Lapok, 16(289-299):7, 1965","cited_arxiv_id":null,"evidence_quote":"Classifies graphs with no two disjoint cycles, identifying apex-forests and wheels as the motivating cases."},{"cited_title":"Quickly excluding a planar graph.Journal of Combinatorial Theory, Series B, 62(2):323–348, 1994","cited_arxiv_id":null,"evidence_quote":"Provides the expander-based lower bound, which motivates restricting attention to planar H with few disjoint cycles."}],"review_version":2}