Extremal graph theory · longest cycles · degree-sum conditions

Ore-Type Bondy Longest-Cycle Conjecture

Collaboration beta

In a k-connected graph with the required degree-sum bound, must every component outside a longest cycle avoid paths on k vertices?

σ_{k + 1} (G) \geq n + k (k - 1) \Rightarrow p (G - V (C)) \leq k - 1

Known results and sources

The conjecture asks whether a strong Ore-type degree-sum condition forces every component outside every longest cycle to contain no path on k vertices.

Research problem

Exact mathematical statement

\sigma_{k+1}(G)\ge n+k(k-1)\quad\Longrightarrow\quad p\bigl(G-V(C)\bigr)\le k-1

for every longest cycle $C$ in every $k$ -connected graph $G$ of order $n$ , where $\sigma_{k+1}(G)$ is the minimum degree sum of an independent set of $k+1$ vertices, with value $+\infty$ when no such independent set exists. Equivalently, no component of $G-C$ contains a path on $k$ vertices.

Problem infographic

Problem at a glance

A dark graph-theory plate centers a large graph G with a gold cycle C and an exterior component H. A green path inside H is marked k vertices with a question mark, while a small cobalt inset highlights k+1 pairwise nonadjacent vertices for the degree-sum quantity σₖ₊₁. The conjectural degree-sum implication is shown as an open question, with the Ore-type k=3 case marked known and the general case marked open. — The Ore-type Bondy longest-cycle conjecture asks whether σₖ₊₁(G) ≥ n+k(k−1) forces every component outside every longest cycle C to avoid a path on k vertices. The highlighted exterior path is the forbidden configuration being asked about, not a counterexample. The Ore-type case k=3 is known; the statement for all k remains open.

Current mathematical picture

Where work on Ore-Type Bondy Longest-Cycle Conjecture stands

Open conjecture

This curated overview retains the open Ore-type longest-cycle conjecture, its conditional active chamber, exact degree-pressure tools, the current work-reported two-chain and protected-edge results, a boundary-safe fixed-endpoint argument, fragile separator and tripod candidates, two Revision-10 corrections, and the current rooted and switch-certificate obligations. Every project-derived [P] item remains provisional narrative evidence here rather than independently reviewed or kernel-checked proof. The 2026 sufficiently-large minimum-degree result is recorded only as a preprint-reported specialization, not as a checked proof of either the specialization or the full Ore-type conjecture. Revision 10 supersedes Revision 9's general multi-chain closure claim and refutes its overbroad rooted connected-deletion implication with rooted K_{2,3}. The conjecture remains open.

Strongest supported footholdBoundary-safe fixed-endpoint proof added

Revision 10 gives a complete project-derived argument that bad pairs in alpha<=3 graphs are supported by minimum 3-cuts.

Evidence posture · Reported result

Leading routeConditional active-chamber route

Develop exact degree pressure and attachment structure inside alpha(G)=k+3, |A|=k, alpha(H)<=3, n<=k^2+3k while preserving all upstream source gates.

Route status · Active route

Useful failureRevision-9 common rooted-gateway route

The route is eliminated in its Revision-9 form because its connected-deletion premise is refuted by rooted K_{2,3}.

Route status · Refuted route

Main reductionProtected-edge conservation retained

The corrected q_edge invariant closes low edge excess and isolates exact q_edge=1 and q_edge=2 frontiers.

Evidence posture · Reported reduction

Completed special caseOrdinary alpha<=2 rooted case retained

The Revision-8 endpoint theorem remains available when alpha(B)<=2, but cannot be extended merely from alpha(B-c)<=2.

Evidence posture · Reported special case

Priority open bridgeComplete literal p>=3 switch certificates

Define every live p>=3 saturated six/seven-edge state and supply a literal cyclic traversal or reproducible exact certificate preserving all rigid blocks.

Task status · Ready to work on

Earlier research stageRooted K_{2,3} refutes the connected-deletion extension

A five-vertex rooted K_{2,3} witness invalidates Revision 9's endpoint extension and its downstream gateway deductions.

Revision-history stage 12

Work mapped so far

Ore-Type Bondy Longest-Cycle Conjecture in numbers

6.6kretained lines of mathematical investigation6,594 in the current working snapshot

Argument development: 5,538 · 84%
Explored or eliminated routes: 271 · 4%
Computational analysis: 86 · 1%
Open obligations: 260 · 4%
Definitions and setup: 439 · 7%

28selected mapped statements12routes investigated9reported milestones10open questions6contribution-ready tasks

How this is measured

This measures retained mathematical investigation, not proximity to a proof. Code, data, logs, repeated text, operational instructions, and generated presentation copy are excluded.

Proposed byJ. A. BondyProposed1980Status checkedAug 2, 2026

Source recordedAug 2, 2026

Recommended next task

Complete literal p>=3 switch certificates

Define every live p>=3 saturated six/seven-edge state and supply a literal cyclic traversal or reproducible exact certificate preserving all rigid blocks.

Suggested move: Begin with k=9 low slack and k=10 high slack; expand every table symbol to its tested edge and complete cycle.

What would count as progress

Enumerate the full state including orientations and connector orders.
Give one literal cycle or retained machine certificate per state.
Check artificial-edge removal, rigid-block restoration, and strict length comparison.

Argument map and routes

How the current approaches connect

Claims, reductions, open questions, active routes, and narrowed alternatives in one mathematical map.

Visible working map

Research route map

28 selected steps

Selected claims, active routes, useful failures, and open questions from the current research map. Arrows appear only for explicitly recorded relationships.

Scroll horizontally to explore the route

Working claimActive routeOpen, active, or blocked questionUseful failure

Working overview, not proof. The map shows selected recorded relationships; more nodes or edges do not establish correctness or completion.

Active routeConditional active-chamber route

Develop exact degree pressure and attachment structure inside alpha(G)=k+3, |A|=k, alpha(H)<=3, n<=k^2+3k while preserving all upstream source gates.

Route status · Active route

Active routeExact pair/triple pressure

Use ceiling-sensitive lifting and the canonical deficit to constrain independent pairs, triples, and separator patterns.

Route status · Active route

Active routeLiteral p>=3 switch certificates

Complete the live multi-chain rows with exact state definitions, tested edges, literal cycles, orientations, and restoration checks.

Route status · Active route

Active routeProtected-edge excess hierarchy

Organize closure by q_edge, using conservation to close q_edge<=0 and isolate q_edge=1 and q_edge=2 frontier states.

Route status · Active route

Active routeExceptional rooted independence-three route

Use block embedding, two external endpoint neighborhoods, 3-connectivity, and exact pressure to classify or penalize rooted K_{2,3}-type obstructions.

Route status · Active route

Explored alternatives

Other routes

7 recorded

Narrowed routeSaturated two-chain packet

Retain only the literal p=2 low/high-slack rows as a localized project proof certificate pending independent line audit.

Route status · Narrowed route

Narrowed routeFixed endpoints to minimum 3-cuts

Use the boundary-safe fixed-endpoint theorem to place every bad endpoint pair in a 3-cut.

Route status · Narrowed route

Not yet justifiedThree-branch separator classification

Retain the candidate classification and numerical elimination only conditionally until every endpoint orbit receives a literal route or obstruction.

Route status · Not yet justified

Browse 4 more explored routes

Route held in reserveThree-endblock tripod exclusion

Keep the exact tripod structure, but pause its exclusion until endpoint-support routing and integer-pressure applications are audited.

Route status · Route held in reserve

Refuted routeRevision-9 common rooted-gateway route

The route is eliminated in its Revision-9 form because its connected-deletion premise is refuted by rooted K_{2,3}.

Route status · Refuted route

Route held in reserveIndependent global gates

Residual two-branch routing, high-connectivity weaving, mixed cuts, multi-hard allocation, deep-cut capacity, and source/lifting audits remain separate open workstreams.

Route status · Route held in reserve

Narrowed routeSeparate minimum-degree specialization

Retain the 2026 preprint only as external context for a weaker sufficiently-large-order minimum-degree theorem, not as closure of the Ore route.

Route status · Narrowed route

Route statements and reductions

Statements the next route can inspect and build on

Route statementActive conditional chamber

The retained route works conditionally in the chamber alpha(G)=k+3, |N_C(H)|=k, alpha(H)<=3, and n<=k^2+3k, with an attachment matching saturating all k attachments.