gpt 6 astra ultra attempt on Math-1076

Jones' conjecture

Definitions and mathematical statement

Let $G=(V,E)$ be a finite simple planar graph, so it admits an embedding in the plane without crossing edges. A cycle means a connected $2$-regular subgraph. A cycle packing is a collection of cycles with pairwise disjoint vertex sets; write $cp(G)$ for the largest possible number of cycles in such a collection. The quantity counts cycles, not their total number of vertices or edges.

A feedback vertex set is a set $X\subseteq V$ such that $G-X$ is acyclic, where deleting vertices also deletes all their incident edges. Write $cc(G)$ for the smallest size of a feedback vertex set. Equivalently, $X$ must meet the vertex set of every cycle in $G$.

Jones' conjecture is the uniform inequality \[ cc(G)\leq2\,cp(G) \qquad\text{for every finite simple planar graph }G. \] Thus, if the largest family of vertex-disjoint cycles has $k$ members, at most $2k$ vertices should suffice to hit all cycles, including overlapping cycles outside a chosen packing. The vertices of the hitting set may be anywhere in $G$; they need not be selected only from one optimal packing.

For a forest both parameters are zero. Disconnected graphs are allowed, with both parameters adding over components. The elementary reverse bound $cp(G)\leq cc(G)$ follows because disjoint cycles require distinct deleted vertices. The proposed factor two is the additional conclusion supplied by planarity.

Short English statement

In every planar graph, can all cycles be destroyed by deleting at most twice as many vertices as the maximum number of vertex-disjoint cycles?

Research attempt: an exact cactus case and a sharp planar example

Scope and literature check.

GPT-6 Astra Ultra, 1 October 2026. Packing is by vertex-disjoint cycles, and the hitting set may use any vertices. Bärnkopf and Győri [S3] prove Jones' bound for based planar graphs, including Halin graphs; their current preprint is a primary source for that restricted result. The argument below proves the stronger equality $cc=cp$ for cactus graphs and then examines why the obvious packing-to-hitting construction does not produce a uniform factor for general planar graphs. No claim of improving the cited results is made.

1. The universal easy inequality.

Any feedback vertex set must meet each member of a vertex-disjoint cycle packing. Those intersections require different vertices, so $cp(G)\le cc(G)$. Both parameters add over connected components: packings from components may be combined, and cycles cannot cross between components. Thus it suffices to work in one component, and forests provide the zero base case for induction.

2. Exact min--max equality for cactus graphs.

A cactus is a graph in which every block is either a single edge or a cycle; in particular distinct cycles meet in at most one vertex. In a connected cactus containing a cycle, choose an end cycle $C$ in the block-cut structure: there is a vertex $v\in V(C)$ such that no vertex of $C-v$ belongs to any other cycle. To justify existence, take the minimal subtree of the block-cut tree connecting all its cycle-block nodes. An end cycle node of that subtree has at most one direction leading to another cycle block, and the first cut vertex in that direction serves as $v$. If there is only one cycle, take any vertex on it. Acyclic branches attached at other vertices do not affect the assertion.

Set $H=G-v$. Every cycle of $H$ avoids every vertex of $C-v$, because those vertices belonged to no other cycle of $G$. Hence a maximum packing in $H$ may be augmented by $C$ in $G$, giving $cp(G)\ge1+cp(H)$. Conversely, at most one member of any disjoint packing in $G$ can use $v$, and the rest form a packing in $H$. Thus \[ cp(G)=1+cp(H). \] A feedback vertex set of $H$, together with $v$, destroys every cycle of $G$, so $cc(G)\le1+cc(H)$. The graph $H$ is again a possibly disconnected cactus. Induction and the universal reverse inequality now give \[ cp(G)\le cc(G)\le1+cc(H)=1+cp(H)=cp(G). \] Therefore $cc(G)=cp(G)$ for every cactus. This proof is constructive: repeatedly record an end cycle and its attachment vertex, delete that vertex, and recurse on the components.

3. Why factor two is necessary in the planar target.

In $K_4$, no two cycles are vertex-disjoint, because every cycle has at least three vertices, while the graph has only four. Hence $cp(K_4)=1$. Deleting one vertex leaves a triangle, so a feedback set has size at least two. Deleting any two vertices leaves at most one edge, proving $cc(K_4)=2$. This planar graph attains the proposed factor. Taking disjoint unions shows the sharpness persists at every positive packing number, rather than being an isolated small case.

4. A tested limitation of using one maximal packing.

Let $C_1,\ldots,C_t$ be an inclusion-maximal vertex-disjoint packing. Their combined vertex set hits every cycle, since a cycle disjoint from the union could be added. This proves only $cc(G)\le\sum_i|V(C_i)|$. Cycle lengths are unbounded even in planar graphs: for $C_n$ this construction uses all $n$ vertices while $cc(C_n)=cp(C_n)=1$. Thus maximality supplies a hitting set but no constant-size budget per packed cycle. Replacing each packed cycle by two arbitrarily chosen vertices has no demonstrated hitting property for cycles that overlap it elsewhere.

Verification and first remaining gap.

The script [S4] independently enumerates cycle vertex sets and feedback sets for $K_4$, a cactus of three triangles sharing one vertex, and a connected cactus with two disjoint triangle blocks. It obtains $(cp,cc)=(1,2),(1,1),(2,2)$. The induction uses the block structure, which general planar graphs lack. The missing step is controlling intersecting cycles inside non-cactus blocks with a budget of two vertices per packed cycle.

Final status

UNRESOLVED. The cactus equality and sharpness of factor two are proved; the general planar packing-to-hitting inequality is not established. Completion estimate: no defensible global percentage.

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, supplied problems.json, record 3170 (OPG-638), OpenGarden collection. Catalogue identity and source transcription; CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Open Problem Garden, Jones' conjecture. Original problem and discussion; the mathematical formulation below is expanded from the supplied source record. http://www.openproblemgarden.org/op/jones_conjecture.
• S3 P. Bärnkopf and E. Győri, Jones' conjecture for Halin graphs and a bit more, arXiv:2401.07376, version 4 (August 2026). Checked 1 October 2026. https://arxiv.org/abs/2401.07376.
• S4 GPT-6 Astra Ultra, exact cycle-packing and feedback-set checks, 1 October 2026: scripts/check_attempt_batch02_connectivity_2026_10_01.py in this repository; run with Python 3.