Proof of a conjecture of Voss on bridges of longest cycles

Jie Ma; Rongxing Xu

REVIEW 2 major objections 4 minor 40 references

Proof of a conjecture of Voss on bridges of longest cycles

T0 review · 2 major / 4 minor · reviewed 2026-08-15 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read 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.

desk verdict 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. read the letter →

arxiv 2509.06345 v1 pith:7BJYLSKJ submitted 2025-09-08 math.CO

Jie Ma , Rongxing Xu This is my paper · ORCID

classification math.CO MSC 05C3805C40

keywords longestcyclesbridgesofacycleoverlapgraphcovering2-connectedgraphsVossconjecturespanbridge

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

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)|$.

What carries the argument

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$.

What would settle it

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.

Watch

Extended reading notes

Core claim

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.

Load-bearing premise

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.

Editorial extensions

If this is right

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.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

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.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the 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.

The 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.

The 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.

Net: 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.

Referee Report

2 major / 4 minor

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.

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 (2)

[Section 4.1 (and 4.2, 4.3)] 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.
[Theorem 5 statement and Sections 4.1-4.3] 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.

minor comments (4)

[Section 4, definition of "witness"] 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 1, proof of Theorem 3] 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 4.3, Claim 3d] 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 4.2 and 4.3] 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.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the paper is a self-contained proof; the reader-identified induction gap is a correctness concern, not a reduction of the theorem to its assumptions.

full rationale

The derivation chain is standard and self-contained: Theorem 3 is reduced to the cycle-covering Theorem 4 by counting edges in symmetric differences, and Theorem 4 is derived from conditions (C1)-(C2) of the stronger Theorem 5. Theorem 5 is then proved by an explicit induction whose base cases s=1 and s=2 are constructed directly and whose inductive step (Sections 4.1-4.3) invokes the induction hypothesis on subgraphs G1 and G2 with strictly fewer L-bridges. The auxiliary digraph D_eta, Lemma 7's cut bound, and Lemma 8's dipath-cover bound are established internally from elementary degree and dicycle arguments; none of these statements assumes Conjecture 2 or Theorem 4. No parameter is fitted and no quantity called a prediction is instead an input: lambda(B_i) enters exactly as |E(T_i)| for the chosen maximum tree T_i, and the covering multiplicities are proved, not assumed. The only self-citation is reference [22] in Section 5, which is used merely as a pointer to related work on longest-cycle intersections and plays no role in the proof. The skeptic's concern about the tree property of O_{G1}(L) and O_{G2}(L) after splitting T2 is a possible gap in the induction's hypotheses; if it is real, it makes the proof incomplete, not circular, because it does not make the conclusion equal to an assumption or to a fitted input. Therefore the circularity score is 0.

Assumptions & free parameters 0 free parameters · 6 assumptions · 2 invented entities

The central claim does not rely on fitted constants or external empirical inputs. It rests on standard graph theory plus two unproved structural facts, H being 2-connected and the split graphs retaining tree overlap graphs, that the paper asserts during the induction. The auxiliary digraph and dicycle types are internal tools.

assumptions (6)

standard math Standard ZFC set-theoretic mathematics and finite graph theory.
Background framework for all definitions and proofs.
standard math Handshaking Lemma: a finite graph has an even number of odd-degree vertices.
Used in Lemma 7 to rule out odd cuts of size 3.
standard math Every finite tree with at least two leaves has a leaf; removing an edge splits the leaf set into two non-empty sets.
Used in Claim 1 and Lemma 8 to locate leaves of the overlap tree and to count path covers.
domain assumption H = L union T_i is 2-connected.
Stated without proof in the proof of Theorem 3 and required to apply Theorem 4. It is plausible from 2-connectivity of G and the bridge and overlap conditions, but the paper gives no explicit argument.
domain assumption The graphs G1 and G2 obtained after deleting a leaf bridge and splitting T2 satisfy the induction hypotheses, including having tree overlap graphs and the stated bridge sets.
Applied in Sections 4.1, 4.2, and 4.3 to use the induction hypothesis, but the tree property of the overlap graphs is not explicitly verified.
standard math For a finite bridge B_i, a largest tree T_i with leaves exactly the attachments exists.
Used to define T_i in the reduction; follows from finiteness and taking a minimal subtree connecting all attachments.

invented entities (2)

Auxiliary multidigraph D_eta
purpose: Generates, for any tree with labeled leaves, a family of leaf-to-leaf dipaths covering each edge at least four times, as in Lemma 8.
Internal combinatorial construction used in the proof of Theorem 5; it has no empirical or external falsifiable content.
Four dicycle types 00, 01, 10, 11 relative to an attachment vertex
purpose: Classifies directed cycles by their orientation through a fixed attachment vertex, allowing condition (C4) to enforce exact counts.
Internal proof bookkeeping device; no independent evidence is required or provided.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Proof of a conjecture of Voss on bridges of longest cycles." pith.science (2026). https://pith.science/paper/7BJYLSKJ

@misc{pith2026250906345,
  author       = {Pith},
  title        = {Pith review of: Proof of a conjecture of Voss on bridges of longest cycles},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/7BJYLSKJ}},
  note         = {Machine review of arXiv:2509.06345}
}

abstract

Bridges are a classical concept in structural graph theory and play a fundamental role in the study of cycles. A conjecture of Voss from 1991 asserts that if disjoint bridges $B_1, B_2, \ldots, B_k$ of a longest cycle $L$ in a $2$-connected graph overlap in a tree-like manner (i.e., induce a tree in the {\it overlap graph} of $L$), then the total {\it length} of these bridges is at most half the length of $L$. Voss established this for $k \leq 3$ and used it as a key tool in his 1991 monograph on cycles and bridges. In this paper, we confirm the conjecture in full via a reduction to a cycle covering problem.

Figures

Figures reproduced from arXiv: 2509.06345 by the authors.

**Figure 1.** Two examples for Conjecture 2 The main result of this paper resolves Conjecture 2 completely. Theorem 3 Conjecture 2 holds for all positive integers k. It is worth emphasizing that we prove this result by reducing the problem to one involving specified cycle coverings, which we then solve. To state this result formally, we need to introduce one more concept: the symmetric difference of two subgraphs H1 and H2 of a g… view at source ↗

**Figure 2.** Examples of Dη , where each η is a partition of 10. It is easy to check that Dη is a digraph in which every vertex has both in-degree 2 and out-degree 2. Note that if pi = pi+1 = 1 for some i, then Dη contains multiple arcs. See [PITH_FULL_IMAGE:figures/full_fig_p005_2.png] view at source ↗

**Figure 3.** Illustration for the construction of C. The blue dicycle corresponds to (3) and the red one corresponds to (4). By the construction of C, it is easy to check that C satisfies (C3)-(C4), we omit the details and only focus on the verification of (C1) and (C2). Observe that for i = 1, 2, the underlying paths in C|Ti and P(Ti , ηi , ℓi ) are identical, so there is a natural one-to-one correspondence between C|Ti and P(T… view at source ↗

Figures from the paper (4 more)

**Figure 4.** Figure 4: Case 1 Let G1 be the subgraph of G induced by the edges in L, T21, T3 , . . . , Ts and G2 be the subgraph of G induced by the edges in L, T22, T1 . By induction hypothesis, there exists C i ⊆ C(Gi ) which is feasible for (Gi , L), i = 1, 2. We have the following. Claim…

**Figure 5.** Figure 5: Illustration for the construction of G ∗ , G ∗ 1 and G ∗ 2 . and b plays the role of v k qk−1 , and the remaining attachments of T ∗ 22 along L[u k pk , b− ] play the role of v k 1 , v k 2 , . . . , v k qk−2 in order, respectively. Note that both a and b are two attach…

**Figure 6.** Figure 6: Illustration for the construction of #—C new 1 (left) and #—C new 2 (right). The underlying graph of the green diptahs in the left figure are both Q1 , while those that in the right figure are both Q2 . 13 [PITH_FULL_IMAGE:figures/full_fig_p013_6.png]

**Figure 7.** Figure 7: Illustration for the choice of x and xa, xb. The red path is Q. contains either no or two attachments of Tj for j ̸= 2 as (C3) holds for C 11 1 (a) and C 00 2 (a). Similarly, we can verify that C new 2 satisfies (C3). Now we show that C satisfies (C4). This statement h…

Review history (2 revisions) →

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

40 extracted references · 34 canonical work pages

[1]

B. R. Alspach and C. D. Godsil, editors.Cycles in graphs, volume 115 ofNorth-Holland Mathematics Studies. North-Holland Publishing Co., Amsterdam, 1985. Papers from the workshop held at Simon Fraser University, Burnaby, B.C., July 5–August 20, 1982, Annals of Discrete Mathematics, 27

work page 1985
[2]

Auslander and S

L. Auslander and S. V. Parter. On imbedding graphs in the sphere.J. Math. Mech., 10:517–523, 1961

work page 1961
[3]

L. Babai. Long cycles in vertex-transitive graphs.J. Graph Theory, 3(3):301–304, 1979

work page 1979
[4]

J. A. Bondy. Beautiful conjectures in graph theory.European J. Combin., 37:4–23, 2014

work page 2014
[5]

J. A. Bondy and R. C. Entringer. Longest cycles in 2-connected graphs with prescribed maximum degree.Canadian J. Math., 32(6):1325–1332, 1980. 18

work page 1980
[6]

J. A. Bondy and U. S. R. Murty.Graph theory, volume 244 ofGraduate Texts in Math- ematics. Springer, New York, 2008

work page 2008
[7]

G. Chen, R. J. Faudree, and R. J. Gould. Intersections of longest cycles ink-connected graphs.J. Combin. Theory Ser. B, 72(1):143–149, 1998

work page 1998
[8]

G. Chen, L. Sheppardson, X. Yu, and W. Zang. The circumference of a graph with no K3,t-minor.J. Combin. Theory Ser. B, 96(6):822–845, 2006

work page 2006

Show all 40 references

[9]

Chen and X

G. Chen and X. Yu. Long cycles in 3-connected graphs.J. Combin. Theory Ser. B, 86(1):80–99, 2002

2002
[10]

G. Chen, X. Yu, and W. Zang. The circumference of a graph with noK 3,t-minor, II.J. Combin. Theory Ser. B, 102(6):1211–1240, 2012

2012
[11]

Chiba and T

N. Chiba and T. Nishizeki. A theorem on paths in planar graphs.J. Graph Theory, 10(4):449–450, 1986

1986
[12]

M. DeVos. Long cycles in vertex-transitive graphs.arXiv:2302.04255v1, 2023

2023 arXiv
[13]

A. J. Goldstein. An efficient and constructive algorithm for testing whether a graph can be embedded in a plane. InGraph and Combinatorics Conference, Princeton, NJ, May
[14]

R. L. Graham, M. Gr¨ otschel, and L. Lov´ asz, editors.Handbook of combinatorics. Vol. 1,
[15]

Groenland, S

C. Groenland, S. Longbrake, R. Steiner, J. Turcotte, and L. Yepremyan. Longest cycles in vertex-transitive and highly connected graphs.Bulletin of the London Mathematical Society, https://doi.org/10.1112/blms.70134, 2025

2025 doi
[16]

Elsevier Science B.V., Amsterdam; MIT Press, Cambridge, MA, 1995

1995
[17]

Hopcroft and R

J. Hopcroft and R. Tarjan. Efficient planarity testing.J. ACM, 21(4):549–568, Oct. 1974

1974
[18]

Gr¨ otschel

M. Gr¨ otschel. On intersections of longest cycles. InGraph theory and combinatorics (Cambridge, 1983), pages 171–189. Academic Press, London, 1984

1983
[19]

Jackson and X

B. Jackson and X. Yu. Hamilton cycles in plane triangulations.J. Graph Theory, 41(2):138–150, 2002

2002
[20]

Jackson and N

B. Jackson and N. C. Wormald. Longest cycles in 3-connected planar graphs.Journal of Combinatorial Theory, Series B, 54(2):291–321, 1992

1992
[21]

Kawarabayashi and K

K. Kawarabayashi and K. Ozeki. 4-connected projective-planar graphs are Hamiltonian- connected.J. Combin. Theory Ser. B, 112:36–69, 2015

2015
[22]

Kawarabayashi, J

K. Kawarabayashi, J. Niu, and C.-Q. Zhang. Chords of longest circuits in locally planar graphs.European J. Combin., 28(1):315–321, 2007

2007
[23]

Norin, R

S. Norin, R. Steiner, S. Thomass´ e, and P. Wollan. Small hitting sets for longest paths and cycles.arXiv preprint arXiv:2505.08634, 2025

2025 arXiv
[24]

Ma and Z

J. Ma and Z. Zhao. Intersections of longest cycles in vertex-transitive and highly con- nected graphs.arXiv:2508.17438, 2025. 19

2025 arXiv
[25]

D. P. Sanders. On paths in planar graphs.J. Graph Theory, 24(4):341–345, 1997

1997
[26]

Ozeki and C

K. Ozeki and C. T. Zamfirescu. Every 4-connected graph with crossing number 2 is Hamiltonian.SIAM J. Discrete Math., 32(4):2783–2794, 2018

2018
[27]

Thomas and X

R. Thomas and X. Yu. 4-connected projective-planar graphs are Hamiltonian.J. Combin. Theory Ser. B, 62(1):114–132, 1994

1994
[28]

Shabbir, C

A. Shabbir, C. T. Zamfirescu, and T. I. Zamfirescu. Intersecting longest paths and longest cycles: A survey.Electronic Journal of Graph Theory and Applications (EJGTA), 1(1):56–76, 2013

2013
[29]

Thomas, X

R. Thomas, X. Yu, and W. Zang. Hamilton paths in toroidal graphs.J. Combin. Theory Ser. B, 94(2):214–236, 2005

2005
[30]

Thomas and X

R. Thomas and X. Yu. Five-connected toroidal graphs are Hamiltonian.J. Combin. Theory Ser. B, 69(1):79–96, 1997

1997
[31]

Thomassen

C. Thomassen. Configurations in graphs of large minimum degree, connectivity, or chro- matic number. InCombinatorial Mathematics: Proceedings of the Third International Conference (New York, 1985), volume 555 ofAnn. New York Acad. Sci., pages 402–412. New York Acad. Sci., New ...

1985
[32]

Thomassen

C. Thomassen. A theorem on paths in planar graphs.J. Graph Theory, 7(2):169–176, 1983

1983
[33]

W. T. Tutte. A theorem on planar graphs.Trans. Amer. Math. Soc., 82:99–116, 1956

1956
[34]

Thomassen

C. Thomassen. Chords of longest cycles in cubic graphs.J. Combin. Theory Ser. B, 71(2):211–214, 1997

1997
[35]

Voss.Cycles and bridges in graphs, volume 49 ofMathematics and its Applications (East European Series)

H.-J. Voss.Cycles and bridges in graphs, volume 49 ofMathematics and its Applications (East European Series). Kluwer Academic Publishers Group, Dordrecht; VEB Deutscher Verlag der Wissenschaften, Berlin, 1991

1991
[36]

W. T. Tutte. Matroids and graphs.Trans. Amer. Math. Soc., 90:527–552, 1959

1959
[37]

M. C. Wigal and X. Yu. Tutte paths and long cycles in circuit graphs.J. Combin. Theory Ser. B, 158(part 1):313–330, 2023

2023
[38]

H. Whitney. A theorem on graphs.Ann. of Math. (2), 32(2):378–390, 1931

1931
[40]

C. Q. Zhang. Longest cycles and their chords.J. Graph Theory, 11(4):521–529, 1987. 20

1987
[1963]

Contract No

Office of Naval Research Logistics Project, Department of Mathematics, Princeton University. Contract No. NONR 1858-(21), May 16–18, 2 pp

Pith tools

Reviewed August 15, 2026 · model on record in the stance chip above.

[1] [1]

B. R. Alspach and C. D. Godsil, editors.Cycles in graphs, volume 115 ofNorth-Holland Mathematics Studies. North-Holland Publishing Co., Amsterdam, 1985. Papers from the workshop held at Simon Fraser University, Burnaby, B.C., July 5–August 20, 1982, Annals of Discrete Mathematics, 27

work page 1985

[2] [2]

Auslander and S

L. Auslander and S. V. Parter. On imbedding graphs in the sphere.J. Math. Mech., 10:517–523, 1961

work page 1961

[3] [3]

L. Babai. Long cycles in vertex-transitive graphs.J. Graph Theory, 3(3):301–304, 1979

work page 1979

[4] [4]

J. A. Bondy. Beautiful conjectures in graph theory.European J. Combin., 37:4–23, 2014

work page 2014

[5] [5]

J. A. Bondy and R. C. Entringer. Longest cycles in 2-connected graphs with prescribed maximum degree.Canadian J. Math., 32(6):1325–1332, 1980. 18

work page 1980

[6] [6]

J. A. Bondy and U. S. R. Murty.Graph theory, volume 244 ofGraduate Texts in Math- ematics. Springer, New York, 2008

work page 2008

[7] [7]

G. Chen, R. J. Faudree, and R. J. Gould. Intersections of longest cycles ink-connected graphs.J. Combin. Theory Ser. B, 72(1):143–149, 1998

work page 1998

[8] [8]

G. Chen, L. Sheppardson, X. Yu, and W. Zang. The circumference of a graph with no K3,t-minor.J. Combin. Theory Ser. B, 96(6):822–845, 2006

work page 2006