{"id":"741cecdd-6d04-42b7-84d2-5d6c2061d83d","arxiv_id":"2509.06345","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":8.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Voss's 1991 conjecture is true: disjoint bridges of a longest cycle that overlap in a tree pattern have total length at most half the length of the cycle.","lead":"A 34-year-old conjecture about the sizes of bridges attached to longest cycles in 2-connected graphs is now proved in full. The proof works by converting the bridge overlap condition into a cycle covering problem, then solving it with directed-cycle constructions.","discovery_kind":"first_principles","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The induction in Theorem 5 repeatedly applies the hypothesis to subgraphs G1 and G2 without proving that the T2-split preserves the tree overlap graph; Section 2 itself states this tree condition is required for the induction, yet Section 4 never establishes it.","rationale":"We agree with the reader's weakest assumption. The key step in the proof of Theorem 5 is the induction, and every instance of 'By induction hypothesis' in Section 4 is applied to a subgraph whose overlap graph is asserted to be a tree but never verified. The paper even acknowledges in Section 2 that the induction requires O_L(G1) and O_L(G2) to be trees, so the omission is not a matter of overly terse style but of a missing structural lemma. The concern is load-bearing because a single failure of the tree property would make the recursive construction invalid; it is not an internal contradiction — we see no obvious counterexample and the claim is plausible — but the proof as written is incomplete. The conditional verdict is appropriate: the gap is likely repairable by adding a lemma to Section 4 (or a proof in Claim 1a/1b's vicinity), but until that is supplied the central theorem is not fully established. We therefore recommend no change to the reader's conditional verdict.","tokens_in":19824,"tokens_out":50856,"duration_ms":419455,"concrete_test":"Implement the Section 4.1 split computationally: enumerate all 2-connected graphs on up to 9 vertices, all longest cycles L, and all choices of pairwise vertex-disjoint L-bridges whose overlap graph is a tree. For each instance, choose a leaf T1 and construct G1 and G2 exactly as in Section 4.1 (using the definitions of a and b and the subtrees T21, T22). Check whether O_{G1}(L) and O_{G2}(L) are trees. If any counterexample appears, the induction step fails; if none appears in exhaustive small cases, the missing lemma is plausible but an analytic proof is still required. The same check should then be run on the subdivided constructions in Sections 4.2 and 4.3.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central proof mechanism is an induction on the number of L-bridges in Theorem 5. In Section 4.1 (and again in the parallel cases 4.2 and 4.3), after choosing a leaf T1 and splitting the overlapping bridge T2 into T21 and T22, the paper asserts 'By induction hypothesis, there exists Ci ⊆ C(Gi) which is feasible for (Gi,L), i=1,2.' The induction hypothesis of Theorem 5, however, requires that the L-bridges of Gi are pairwise vertex-disjoint and 'induce a tree in O_{Gi}(L)'. The paper never proves that O_{G1}(L) (on T21,T3,...,Ts) or O_{G2}(L) (on T22,T1) is a tree. This is not a cosmetic omission: splitting T2 can in principle disconnect the overlap graph or create a cycle, depending on how the attachments of T2 are distributed between T21 and T22 and how the remaining bridges sit in the intervals determined by those attachments. The authors themselves flag the requirement in Section 2: 'to ensure that the induction works, both O_L(G1) and O_L(G2) must be trees.' No lemma or remark later supplies this fact. Since every recursive call in Section 4 depends on it, the proof of Theorem 5 — and hence of the Voss conjecture — is incomplete as written.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper claims a proof of Voss's 1991 conjecture: if G is 2-connected, L is a longest cycle, and B1,...,Bk are pairwise vertex-disjoint L-bridges whose vertices induce a tree in the overlap graph O_G(L), then the sum of their lengths λ(Bi) is at most floor(|E(L)|/2). The proof reduces the statement to a cycle-covering theorem (Theorem 4), then proves a strengthened directed version (Theorem 5) by induction on the number of L-bridges. The induction uses an auxiliary multidigraph D_eta and a family of dipaths covering each tree edge at least four times (Lemmas 6-8). The base cases s=1,2 are explicit, and the induction step splits the bridge T2 into two subtrees to obtain smaller graphs G1 and G2.","tokens_in":20111,"tokens_out":49299,"duration_ms":392088,"significance":"If the proof is correct, this settles a conjecture from Voss's 1991 monograph and gives a quantitative tool for longest-cycle problems; the reduction from the length bound to a cycle-covering statement is clean, and the counting argument is parameter-free. The auxiliary digraph and dipath-covering lemmas are elegant and appear sound. However, the paper's central induction step is missing a key structural verification, so the significance is conditional on repairing that gap.","major_comments":[{"comment":"The sentence \"By induction hypothesis, there exists C_i ⊆ C(G_i) which is feasible for (G_i,L)\" applies Theorem 5 to the subgraphs G1 and G2, but the hypotheses of Theorem 5 are not verified. In particular, the paper never proves that the L-bridges T21, T3, ..., Ts of G1 induce a tree in O_{G1}(L), nor that T22, T1 induce a tree in O_{G2}(L). This is load-bearing: every recursive call in Sections 4.1, 4.2, and 4.3 depends on this tree property. The property is not immediate, because splitting T2 changes the attachment sets and can in principle disconnect the overlap graph; the authors themselves flag in Section 2 that \"to ensure that the induction works, both O_L(G1) and O_L(G2) must be trees,\" but no lemma or remark later supplies this fact. A repair is likely possible (for instance, one can argue that all attachments of T3,...,Ts lie in L[b,a] and that every overlap with T2 is witnessed by T2-leaves in L[b,a], so T21 inherits those overlaps), but as written the proof of Theorem 5 is incomplete at a central point.","section":"Section 4.1 (and 4.2, 4.3)"},{"comment":"The induction hypothesis of Theorem 5 also requires the graph G to be 2-connected, but the subgraphs G1, G2, G*1, G*2 are never shown to be 2-connected. This is an additional missing verification. It is likely true in each case (each subgraph consists of a cycle or subdivided cycle plus trees whose leaves lie on that cycle), but the proof should state and justify it explicitly, since the induction cannot be applied otherwise.","section":"Theorem 5 statement and Sections 4.1-4.3"}],"minor_comments":[{"comment":"The definition \"there are no other attachments on the segments L[x,y] or L[y,x]\" is ambiguous: as written, it appears to require both directed segments to contain no other attachments, which is impossible for two distinct attachments on a cycle. The intended meaning (presumably that the relevant directed segment between the two vertices contains no other attachments) should be clarified, since the subsequent definitions of a and b rely on it.","section":"Section 4, definition of \"witness\""},{"comment":"The claim \"Define H as the union of L and T_i for all 1≤i≤k, which is 2-connected\" is asserted without proof. This is a minor gap, but a one-sentence justification would make the reduction self-contained.","section":"Section 1, proof of Theorem 3"},{"comment":"There is a typo in the line \"T_2[v^1_{q1}, v^{k-1}_{q_{k-1}}] = T_2[a^{01}_2, a^{01}_2]\" — the right-hand side should presumably be T_2[a^{00}_2, a^{01}_2], not T_2[a^{01}_2, a^{01}_2].","section":"Section 4.3, Claim 3d"},{"comment":"The verification that the newly constructed dicycles C_new_i satisfy (C2) and (C3) is described as \"analogous\" and largely omitted. Given the intricacy of the case analysis, a more explicit verification for the new dicycles would improve readability and confidence, even if the arguments are straightforward extensions of the earlier ones.","section":"Section 4.2 and 4.3"}],"recommendation":"major_revision","confidential_remarks":"The main concern is the missing tree-preservation lemma in the induction step of Theorem 5. I attempted to construct a concrete counterexample to the claim that the overlap graphs of G1 and G2 are trees, but in the natural configurations the property held; this suggests the gap is repairable with a dedicated lemma rather than a fatal error. However, the current manuscript is not complete as written, and the missing lemma is central rather than cosmetic. I would ask the authors to add and prove the structural lemma before reconsidering the paper."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Ma and Xu prove Voss's 1991 conjecture in full: for a longest cycle L in a 2-connected graph, pairwise disjoint L-bridges that induce a tree in the overlap graph have total length at most |E(L)|/2. Voss had only the cases k≤3. The proof is via a new cycle-covering theorem (Theorem 4), which says that when the bridges are trees, there is a collection of cycles in which every L-edge is covered exactly twice, every bridge edge at least four times, and each covering cycle C has L△C a cycle. The reduction from the conjecture to this covering statement is clean, and the counting argument that derives Theorem 3 from it is short and correct. The construction of the auxiliary digraph and the proof that the associated dipath family covers each tree edge at least four times (Lemma 8) are solid and genuinely new.\n\nThe soft spot is the induction inside the proof of Theorem 5. After choosing the leaf bridge T1 and splitting the overlapping bridge T2 into T21 and T22, the proof applies the induction hypothesis to G1 on L,T21,T3,...,T_s and G2 on L,T22,T1. The induction hypothesis requires that the bridges in each of these subgraphs induce a tree in the corresponding overlap graph. That condition is never verified in the paper, even though Section 2 explicitly says the induction needs it. This is not a cosmetic omission: splitting T2 can in principle disconnect the overlap graph or create a cycle, depending on how the attachments are distributed. The property probably follows from the way a and b are chosen, but a lemma needs to be written out. Until it is, the induction step is not fully justified. There are also a few places where verification is skipped entirely (\"we omit the verification\"), which is acceptable in principle but adds risk in a proof of this intricacy.\n\nThe citation pattern is fine; the only self-citation is in the concluding remarks and is not load-bearing. The proposed applications to intersection problems of longest cycles are clearly labelled as speculative.\n\nNet: this is a genuine result, likely correct, with a repairable but real gap in the inductive step. It deserves a serious referee, who should ask for the missing tree-preservation lemma and for the omitted checks in Section 4 to be expanded. If that holds up, the paper should be accepted.","headline":"Genuine proof of Voss's long-standing conjecture via a clever cycle-covering reduction, but the induction in Theorem 5 needs a missing tree-preservation lemma before the proof is complete.","tokens_in":20660,"tokens_out":9536,"would_cite":true,"duration_ms":78424,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C38","05C40"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper proves Voss's 1991 conjecture: in a 2-connected graph, vertex-disjoint bridges of a longest cycle that form a tree in the overlap graph have total length at most half the cycle.","keywords":["longest cycles","bridges of a cycle","overlap graph","cycle covering","2-connected graphs","Voss conjecture","span of a bridge"],"falsifier":"A single $2$-connected graph with a longest cycle $L$ and pairwise vertex-disjoint $L$-bridges that induce a tree in $O_G(L)$ but have total length greater than $\\lfloor |E(L)|/2 \\rfloor$ would refute the main theorem; the paper's extremal examples show equality is attainable, so a counterexample search should probe configurations just beyond those. A second, more local check targets the recursion: a bridge configuration in which the split used in Section 4.1 yields a smaller subconfiguration whose overlap graph is not a tree would show the proof of Theorem 5 needs repair even if the conjecture is true.","tokens_in":19603,"feed_emoji":"🔄","tokens_out":20986,"duration_ms":159743,"temperature":0.7,"pith_summary":"The paper proves a conjecture that Voss put forward in 1991 and used as a tool in his monograph on cycles and bridges. The conjecture says that, in a $2$-connected graph $G$ with longest cycle $L$, any collection $B_1,\\dots,B_k$ of pairwise vertex-disjoint $L$-bridges — pieces of $G$ attached to $L$ at designated vertices, namely chords or components of $G-V(L)$ with their edges into $L$ — that form a tree in the overlap graph $O_G(L)$ must satisfy $\\sum_{i=1}^k \\lambda(B_i) \\le \\lfloor |E(L)|/2 \\rfloor$, where $\\lambda(B)$ measures the bridge by the largest number of edges in a tree on it whose leaves are exactly its attachments on $L$. Voss himself proved the cases $k \\le 3$; the paper settles all $k$. The proof works by reducing the conjecture to a cycle-covering statement: the bridge configuration admits a family of cycles in which each edge of $L$ appears exactly twice, each bridge edge appears at least four times, and every covering cycle $C$ makes $L \\triangle C$ a cycle. Since $L$ is a longest cycle, no covering cycle can beat $L$ in length, and a double-counting argument then forces the total bridge length to be at most half of $|E(L)|$.","feed_headline":"Proof: tree-like bridges of a longest cycle stay within half","feed_subtitle":"A 1991 conjecture of Voss holds for any number of bridges; the proof reduces to a double-cover by cycles.","key_machinery":"The proof engine is an auxiliary multidigraph $D_\\eta$ built from a partition $\\eta=(p_1,\\dots,p_k)$ of the number of leaves of a bridge tree: its vertices sit in $k$ consecutive blocks of sizes $p_i$, with arcs back and forth along each block and two arcs joining consecutive blocks. Every vertex of $D_\\eta$ has in-degree and out-degree $2$, giving Lemma 6 (every arc lies on two dicycles that share only that arc) and then Lemma 7 (every nontrivial vertex cut of $D_\\eta$ is crossed by at least four edges). Labeling the leaves of a tree $T$ by the vertices of $D_\\eta$ and taking the dipaths between leaves whose labels are joined by an arc yields Lemma 8: a family of leaf-to-leaf dipaths covering every edge of $T$ at least four times, which supplies the bridge part of the covering cycles. The induction then uses the four directed-cycle types (00, 01, 10, 11) with respect to an attachment vertex; condition (C4), exactly one cycle of each type at each attachment, tells the proof which cycles to delete and which symmetric differences to glue in when two smaller feasible families are combined along the split edges of $T_2$.","core_discovery":"The central result, Theorem 3, is that Voss's conjecture holds for every positive integer $k$, obtained through a first-principles reduction to a cycle-covering problem. The covering statement (Theorem 4, strengthened to directed cycles as Theorem 5) is the discovery that carries the argument: if $T_1,\\dots,T_s$ are pairwise vertex-disjoint $L$-bridges that are themselves trees whose leaves are exactly their attachment vertices on $L$, and that induce a tree in $O_G(L)$, then there exists a family $\\mathcal{C}$ of directed cycles of $G$ such that (C1) every edge of $L$ lies in exactly two cycles of $\\mathcal{C}$ and every edge outside $L$ lies in at least four; (C2) for each covering cycle $C$, the symmetric difference $L \\triangle C$ is a cycle; (C3) each covering cycle contains either no attachment or exactly two attachments of each bridge; and (C4) for each of the four orientation types and each attachment vertex, exactly one covering cycle of that type is present at that vertex. Theorem 5 is proved by induction on the number of bridges, with explicit cycle constructions for one and two bridges and, for three or more, a case analysis that isolates a leaf bridge $T_1$ of the overlap tree, cuts the bridge $T_2$ overlapping it into two subtrees, applies the induction hypothesis to the two smaller subgraphs, and stitches the two feasible families together by deleting paired cycles and inserting their symmetric differences.","pith_inferences":["The authors stop short of proving it, but their cubic-graph calculation suggests a pathway to quantitative forms of the conjecture that two longest cycles in a $k$-connected graph share at least $k$ vertices: bounding how many tree-shaped pieces the overlap graph of $C \\cup D$ splits into would let Theorem 3 be applied piece by piece.","The organization of the proof suggests a verifiable structural lemma: cutting the bridge that overlaps a removed leaf bridge into two subtrees should leave both smaller configurations with tree overlap graphs. The paper does not isolate this fact as a stated lemma in Sections 4.1–4.3, so verifying it for all possible splits would be the most direct check of the induction.","The auxiliary digraph construction is independent of longest cycles: any tree whose leaves are labeled by a $2$-in-$2$-out digraph with the four-edge cut property inherits a leaf-to-leaf path cover with edge multiplicity at least four, so the mechanism could serve other covering problems that need prescribed edge-multiplicity bounds."],"forward_implications":["Voss's conjecture is settled in full: for every $k \\ge 1$, pairwise vertex-disjoint $L$-bridges inducing a tree in $O_G(L)$ satisfy $\\sum_{i=1}^k \\lambda(B_i) \\le \\lfloor |E(L)|/2 \\rfloor$ in any $2$-connected graph.","The bound is best possible: equality is attained by $K_{2,3}$ for one bridge and by a $2k$-cycle with $k$ chords for $k \\ge 2$, while relaxing the tree condition (a disconnected overlap graph, or one containing a triangle as in the Petersen graph) pushes the total bridge length above half of $|E(L)|$.","The covering statement becomes a reusable structural fact: tree-shaped bridge configurations admit cycles that double-cover $L$, quadruple-cover every bridge edge, and satisfy that $L \\triangle C$ is a cycle for every covering cycle $C$, which is exactly the property that makes the longest-cycle comparison work.","For two longest cycles $C,D$ in a $3$-connected cubic graph, if the $C$-bridges of $C \\cup D$ form a tree in the overlap graph, then $|E(C \\cap D)| \\ge |C|/2$ follows from Theorem 3; the paper proposes decomposing overlap graphs into small trees as the route toward the intersection conjectures."],"supporting_citations":[{"why":"Voss's monograph states the conjecture, proves the cases with up to three bridges that this paper extends, and establishes bridges as tools in the study of cycles.","marker":"[35]"},{"why":"Bondy's survey in the Handbook of Combinatorics, where the conjecture is recorded as Conjecture 5.11 and bridges are described as central to cycle theory; the paper positions its result against this framing.","marker":"[14]"},{"why":"Tutte's paper introduces the overlap graph and its planar-graph characterization, the object that the conjecture's hypothesis is stated in terms of.","marker":"[34]"}],"fun_headline_variants":["Voss's bridge conjecture falls to cycle-cover proof","Longest cycle bridges: tree-like case bounded by half","Cycle-cover trick proves Voss 1991 bridge bound","Bridges of longest cycles obey half-length rule"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing step is the induction's silent assumption that after one bridge is removed and the bridge overlapping it is cut into two subtrees, the two smaller bridge configurations again induce trees in their overlap graphs, so the same argument can be reapplied to each.","fun_headline_variants_meta":{"raw":{"variants":["Voss's bridge conjecture falls to cycle-cover proof","Longest cycle bridges: tree-like case bounded by half","Cycle-cover trick proves Voss 1991 bridge bound","Bridges of longest cycles obey half-length rule"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000325,"raw_usage":{"total_tokens":1844,"prompt_tokens":993,"completion_tokens":851,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":609,"completion_tokens_details":{"reasoning_tokens":785}},"tokens_in":609,"tokens_out":851,"duration_ms":7462,"temperature":1.0,"reasoning_tokens":785,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T16:18:54.203983+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"A single $2$-connected graph with a longest cycle $L$ and pairwise vertex-disjoint $L$-bridges that induce a tree in $O_G(L)$ but have total length greater than $\\lfloor |E(L)|/2 \\rfloor$ would refute the main theorem; the paper's extremal examples show equality is attainable, so a counterexample search should probe configurations just beyond those. A second, more local check targets the recursion: a bridge configuration in which the split used in Section 4.1 yields a smaller subconfiguration whose overlap graph is not a tree would show the proof of Theorem 5 needs repair even if the conjecture is true.","supporting_citations":[{"cited_title":"Voss.Cycles and bridges in graphs, volume 49 ofMathematics and its Applications (East European Series)","cited_arxiv_id":null,"evidence_quote":"Voss's monograph states the conjecture, proves the cases with up to three bridges that this paper extends, and establishes bridges as tools in the study of cycles."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Bondy's survey in the Handbook of Combinatorics, where the conjecture is recorded as Conjecture 5.11 and bridges are described as central to cycle theory; the paper positions its result against this framing."},{"cited_title":"Thomassen","cited_arxiv_id":null,"evidence_quote":"Tutte's paper introduces the overlap graph and its planar-graph characterization, the object that the conjecture's hypothesis is stated in terms of."}],"review_version":2}