Restriction on minimum degree in the contractible sets problem
Pith reviewed 2026-05-24 10:32 UTC · model grok-4.3
The pith
For k at least 5, every 3-connected graph with minimum degree at least ceil((2k+1)/3)+2 has a k-vertex contractible set.
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
Core claim
The paper proves that the McCuaig-Ota conjecture holds for every integer k greater than or equal to 5 whenever the 3-connected graph G satisfies the minimum-degree condition delta(G) greater than or equal to ceil((2k+1)/3) plus 2. In other words, under this degree restriction there exists an integer n such that every 3-connected graph on at least n vertices contains a contractible set of exactly k vertices.
What carries the argument
A contractible set W of k vertices, defined so that the induced subgraph on W is connected and G minus W is 2-connected.
If this is right
- For every k at least 5 the existence of an n is guaranteed so that all 3-connected graphs on at least n vertices obeying the degree bound contain a k-vertex contractible set.
- The required minimum degree grows linearly with k at a slope of roughly two-thirds.
- The full conjecture without any minimum-degree restriction remains unsettled by this argument.
Where Pith is reading between the lines
- The same degree bound may allow an explicit (rather than existential) n to be extracted from the proof.
- Graphs that are 3-connected but fall below the degree threshold are the natural candidates in which to search for counterexamples to the unrestricted conjecture.
Load-bearing premise
The graph must be 3-connected and must satisfy the minimum-degree lower bound for the existence argument to apply.
What would settle it
A single 3-connected graph with minimum degree strictly less than ceil((2k+1)/3)+2 that has no k-vertex contractible set, for some fixed k at least 5, would show that the degree threshold is required by the proof method.
read the original abstract
Let $G$ be a $3$-connected graph. A set $W \subset V(G)$ is called contractible if $G(W)$ is a connected graph and $G - W$ is a $2$-connected graph. In 1994, McCuaig and Ota conjectured that for any $k \in \mathbb{N}$ there exists $n \in \mathbb{N}$ such that any 3-connected graph $G$ with $v(G) \geqslant n$ has a $k$-vertex contractible set. It is proved that this holds if $k \geqslant 5$ and $\delta(G) \geqslant \left[ \frac{2k + 1}{3} \right] + 2$.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The manuscript proves that the McCuaig-Ota conjecture holds conditionally: for every k ≥ 5 there exists n such that every 3-connected graph G on ≥ n vertices with δ(G) ≥ ⌈(2k + 1)/3⌉ + 2 possesses a k-vertex contractible set W (i.e., G[W] connected and G − W 2-connected).
Significance. If the proof is correct, the result supplies an explicit minimum-degree threshold that guarantees contractible sets of any fixed size k ≥ 5 in large 3-connected graphs, furnishing a partial affirmative answer to the 1994 conjecture under a natural additional hypothesis.
minor comments (1)
- [Abstract] Abstract: the ceiling function is rendered with square brackets [ ] rather than the standard ⌈ ⌉ notation; this should be clarified in the typeset version.
Simulated Author's Rebuttal
We thank the referee for their careful summary of our manuscript and for recognizing the significance of our conditional result on the McCuaig-Ota conjecture. The report provides no specific major comments or points of criticism, so we have no individual items to address point-by-point. We remain available to supply additional details or clarifications should the referee have further questions.
Circularity Check
No circularity; conditional proof of external conjecture
full rationale
The manuscript states and proves a conditional existence theorem: for k ≥ 5 and δ(G) ≥ ⌈(2k+1)/3⌉ + 2, every sufficiently large 3-connected G has a k-vertex contractible set. This is presented as a partial case of the 1994 McCuaig-Ota conjecture, with the hypotheses explicitly required. No equations, fitted parameters, self-citations, or ansatzes appear in the abstract or claim; the derivation is a direct graph-theoretic argument under stated assumptions and does not reduce any quantity to itself by construction.
Axiom & Free-Parameter Ledger
axioms (1)
- standard math Graphs are finite, undirected, and simple; connectivity is defined via vertex-disjoint paths.
Lean theorems connected to this paper
-
IndisputableMonolith/Foundation/RealityFromDistinction.leanreality_from_one_distinction unclear?
unclearRelation between the paper passage and the cited Recognition theorem.
Theorem 3. Let G be a 3-connected graph, let k ≥ 5 be a natural number and let v(G) ≥ k + 3, δ(G) ≥ [ (2k+1)/3 ] + 2. Then there exists a k-contractible set in the graph G.
What do these tags mean?
- matches
- The paper's claim is directly supported by a theorem in the formal canon.
- supports
- The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
- extends
- The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
- uses
- The paper appears to rely on the theorem as machinery.
- contradicts
- The paper's claim conflicts with a theorem or certificate in the canon.
- unclear
- Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.