A counterexample to the zero forcing versus independence conjecture for cubic and subcubic graphs

Mikko Fischer

A counterexample to the zero forcing versus independence conjecture for cubic and subcubic graphs

T0 review · 0 major / 4 minor · reviewed 2026-07-30 · grok-4.5

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

Pith's one-line read A connected subcubic graph on 24 vertices and a cubic graph on 36 vertices both satisfy Z = α + 2, refuting the conjecture that Z ≤ α + 1.

desk verdict Clean finite counterexamples that kill the TxGraffiti Z ≤ α+1 conjecture for both subcubic and cubic graphs, with the gap-2 value attained and a shipped verification script. read the letter →

arxiv 2607.23664 v1 pith:G3XFFLDC submitted 2026-07-26 math.CO

Mikko Fischer This is my paper · ORCID

classification math.CO MSC 05C6905C50

keywords zeroforcingnumberindependencecubicgraphsubcubicTxGraffitifortcounterexample

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 builds two explicit connected graphs of maximum degree 3 whose zero forcing number is two larger than their independence number. One is a 24-vertex subcubic graph with α = 9 and Z = 11; the other is a 36-vertex cubic graph with α = 15 and Z = 17. Both are obtained from the same skeleton—a triangle with three bridges into identical branches—by attaching a small gadget at each branch tip. The constructions falsify a 2017 conjecture that every connected graph of maximum degree at most 3 (other than K4) satisfies Z ≤ α + 1, and they falsify the cubic-only version of the same claim. A sympathetic reader cares because the bound was believed to hold for all such graphs and had already been proved for large subclasses; these examples show the gap can reach 2 and that no universal +1 bound exists even among cubic graphs.

What carries the argument

The gadget construction G(F): start with a triangle, attach three bridge vertices, and hang two copies of a degree-bounded gadget F from each bridge. Independence numbers are read off by taking a maximum independent set branch by branch; upper bounds on Z come from explicit forcing sets; lower bounds come from enumerating forts inside each branch and exhaustively checking that every set meeting all forts and of size at most 3h + 1 fails to force.

What would settle it

Re-run the accompanying verification script, or independently search for a zero-forcing set of size 10 in the 24-vertex graph or size 16 in the 36-vertex graph; any such set would collapse the claimed values of Z.

Watch

Extended reading notes

Core claim

There exist a connected graph H on 24 vertices with Δ(H) ≤ 3, independence number 9 and zero forcing number 11, and a connected cubic graph G on 36 vertices with independence number 15 and zero forcing number 17. Consequently Z = α + 2 is attained, the conjecture Z ≤ α + 1 fails for both subcubic and cubic connected graphs, and Z ≤ α + 1 is not a universal bound for connected cubic graphs.

Load-bearing premise

The lower bounds rest entirely on a finite computer search that claims to have enumerated every fort inside a branch and verified that none of the surviving candidate sets of size at most 10 (respectively 16) is a zero-forcing set.

Editorial extensions

If this is right

The conjectured bound Z ≤ α + 1 is false for connected graphs of maximum degree 3 and already fails on 24 vertices.
The same bound is false for connected cubic graphs; the smallest cubic counter-example supplied has 36 vertices.
The value Z = α + 2 is attained by both a subcubic and a cubic connected graph.
Any repaired conjecture must either exclude bridges, raise the additive constant, or impose further structural hypotheses such as claw-freeness or bridgelessness.

Reading between the lines

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

Because the construction is built from identical branches joined by bridges, the same pattern can be iterated to produce infinite families with Z − α ≥ 2, which the author defers to a companion paper.
The fort-based counting argument suggests that the gap Z − α is controlled by the fort-hitting number of a single branch; altering the gadget may systematically raise or lower that gap.
A natural next check is whether every 2-connected or 3-connected cubic counter-example requires substantially more vertices than the bridged examples given here.

Share X Bluesky LinkedIn Reddit HN

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

The paper does exactly what the title says: it hands you two small explicit graphs (H on 24 vertices, Δ ≤ 3; G cubic on 36) with Z = α+2, so the 2017 conjecture is dead in both the textual and the Lean-cubic readings. That is the whole contribution, and it is real.

What works well is the construction and the witnesses. The three-branch skeleton with two simple gadgets is easy to draw and easy to check by hand for the upper bounds and the independence numbers; the explicit blue sets and independent sets are written down. The fort reduction is standard and correctly applied: once you accept the branch statistics, the candidate counts follow by elementary casework and the exhaustive check is finite and modest. Shipping pure-Python verification code that rebuilds the graphs from the description and certifies all four numbers is the right way to handle a computational lower bound of this size. Citations are tight and on-point.

The only soft spot is exactly the one the stress-test flags: the lower bounds rest on the completeness of the fort enumeration inside a single branch and on the correctness of the subsequent exhaustive closure checks (17k sets for H, 3M for G). There is no hand proof of those branch numbers and no machine-checked certificate, only the script and the author’s claim of independent re-execution. That is ordinary verification risk for a short note of this type, not a structural hole; anyone who cares can re-run or re-implement in an afternoon. Nothing else is load-bearing.

This is for people who work on zero forcing, power domination, or the TxGraffiti conjectures. It does not reorganize the area, but it settles a concrete open claim and supplies the first cubic examples with gap 2. I would bring it to reading group as a quick “here is how the conjecture dies” item, cite it when the bound comes up, and send it to referees without hesitation. Short, clear, reproducible counterexample notes are what the literature needs.

Referee Report

0 major / 4 minor

Summary. The manuscript defines a three-branch construction G(F) from a triangle and six copies of a gadget F. With F=K3 it obtains a connected subcubic graph H on 24 vertices, and with a five-vertex gadget D it obtains a connected cubic graph G on 36 vertices; both graphs are supplied in graph6 format. Explicit independent sets and zero-forcing sets establish alpha(H)>=9, alpha(G)>=15, Z(H)<=11, and Z(G)<=17. Branch-and-bound and an enumeration based on the Fast–Hicks fort characterization establish the reverse inequalities. The resulting equalities alpha(H)=9, Z(H)=11 and alpha(G)=15, Z(G)=17 give Z=alpha+2 and refute the stated TxGraffiti conjecture in both its subcubic and cubic formulations.

Significance. If the finite computations are accepted, the paper cleanly settles the conjecture in the negative, including the cubic version recorded in the survey's Lean appendix, and shows that the bound can fail by exactly one additional unit. The graphs are small and completely specified by graph6 strings; the upper bounds are supported by explicit witnesses; the lower bounds use a published fort characterization rather than an ad hoc criterion; and the enumeration is reproducible through a self-contained standard-library Python script. The concern about exact fort enumeration is an ordinary verification issue, not an uncovered combinatorial case: the branch searches have only 2^7 and 2^11 subsets, and the paper explains how the 17,712 and 3,112,960 surviving candidates arise. This is a concise and useful counterexample note.

minor comments (4)

[§3, verification discussion] Because the theorem is computational, please include the expected output of verify_note.py, the Python version used, and a checksum or persistent archive reference for the script and the two .g6 files. This would make the already reproducible lower-bound computation easier to audit.
[§3, independence-number computation] The statement that branch and bound 'terminates immediately' is too informal for the upper bounds alpha(H)<=9 and alpha(G)<=15. A sentence identifying the branching order and bound used, or the corresponding function in verify_note.py, would make this part independently intelligible without first reading the code.
[§3, candidate-count formula] The displayed candidate formula counts only sets of sizes 3h and 3h+1, although the preceding sentence says 'at most 3h+1.' Add the explicit observation that smaller sets are already excluded because they must contain at least h vertices from each of the three branches.
[§1 and References] Reference [1] is the 2025 survey recording the conjecture. If a distinct 2017 TxGraffiti source or conjecture number is available, it should also be cited for priority and ease of retrieval.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: explicit finite counterexamples with independent computational verification

full rationale

The paper refutes Conjecture 1 by exhibiting two concrete graphs H = G(K3) and G = G(D), defined combinatorially from a triangle-plus-branches skeleton and two fixed gadgets, then computing four integers (α and Z for each) by finite search. Upper bounds come from explicit zero-forcing sets whose closures are checked; lower bounds use the external fort characterization of Fast–Hicks together with exhaustive enumeration of branch forts and candidate hitting sets. Independence numbers are obtained by branch-and-bound and by explicit maximum independent sets. Nothing is defined in terms of the target bound Z ≤ α + 1, no parameter is fitted to data and then re-predicted, and no load-bearing uniqueness or ansatz is imported from the author’s own prior work. The accompanying Python script rebuilds the graphs and re-certifies the four values; the fort lemma is a published external fact. The derivation is therefore an ordinary explicit counter-model, not a circular reduction.

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

The result is a pure finite-combinatorics counterexample. It rests on standard definitions of zero forcing and independence number, on the published fort characterization of zero-forcing sets, and on the explicit gadget construction introduced in the note. No numerical parameters are fitted; the only non-standard objects are the two gadgets and the three-branch skeleton, both fully defined by edge lists.

assumptions (3)

standard math A set B is a zero-forcing set if and only if it intersects every fort (Fast–Hicks).
Invoked in §3 to convert the lower-bound search into an enumeration of fort-hitting sets inside each branch.
standard math Standard definitions of independence number α(G) and zero-forcing number Z(G), including the forcing rule and closure.
Used throughout; no non-standard variant is introduced.
ad hoc to paper The fort counts t, hitting numbers h, and subset counts m_h, m_{h+1} inside a single branch are exactly the tabulated values (H: t=12,h=3; G: t=156,h=5).
These integers are outputs of the author’s enumeration; they are load-bearing for the candidate counts 17 712 and 3 112 960 and are certified only computationally.

invented entities (2)

Gadget F with attachment vertex z (and the two concrete gadgets K3 and D) independent evidence
purpose: Local building block that forces the global degree and independence/zero-forcing behaviour of the three-branch construction.
Defined in §2 by explicit edge sets; not previously standard objects in the literature.
Three-branch skeleton G(F) (triangle + three bridges + six copies of F) independent evidence
purpose: Global graph that multiplies the per-branch fort lower bound by three and yields the counterexamples H and G.
Introduced in §2; the counterexample property is verified directly on the resulting finite graphs.

how reviews work

0 comments

Cite this review

Pith. "Pith review of A counterexample to the zero forcing versus independence conjecture for cubic and subcubic graphs." pith.science (2026). https://pith.science/paper/G3XFFLDC

@misc{pith2026260723664,
  author       = {Pith},
  title        = {Pith review of: A counterexample to the zero forcing versus independence conjecture for cubic and subcubic graphs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/G3XFFLDC}},
  note         = {Machine review of arXiv:2607.23664}
}

read the original abstract

We exhibit a connected graph on 24 vertices with maximum degree 3, independence number 9 and zero forcing number 11, refuting a 2017 conjecture of TxGraffiti recorded as Conjecture 2 of the survey of Davila, Brimkov and Pepper. The same construction with a different gadget gives a connected cubic graph on 36 vertices with independence number 15 and zero forcing number 17; the conjecture therefore fails also in the cubic form in which the survey's Lean 4 appendix states it. In particular Z <= alpha + 1 is not a universal bound for connected cubic graphs, and the value Z = alpha + 2 is attained.

Figures

Figures reproduced from arXiv: 2607.23664 by the authors.

**Figure 1.** Left: the skeleton of G(F) — a triangle c0c1c2 (black), three vertices r0, r1, r2 (grey), and six copies of the gadget F, each joined to its rj at the attachment vertex. Right: the two gadgets used, giving H = G(K3) on 24 vertices and G = G(D) on 36 vertices. 3. The computation Theorem 2. α(H) = 9 and Z(H) = 11; and α(G) = 15 and Z(G) = 17. Hence Z = α + 2 for both, and Conjecture 1 is false — already on 24 vertices… view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

4 extracted references · 2 linked inside Pith

[1]

Davila, B

R. Davila, B. Brimkov and R. Pepper,In reverie together: ten years of mathematical discovery with a machine collaborator, preprint, arXiv:2507.17780 (2025)

arXiv 2025
[2]

Davila and M

R. Davila and M. A. Henning,Zero forcing in claw-free cubic graphs, Bull. Malays. Math. Sci. Soc.43 (2020), 673–688

2020
[3]

C. C. Fast and I. V. Hicks,Effects of vertex degrees on the zero-forcing number and propagation time of a graph, Discrete Appl. Math.250(2018), 215–226

2018
[4]

Schuerger, N

H. Schuerger, N. Warnberg and M. Young,Zero forcing and vertex independence number on cubic and subcubic graphs, preprint, arXiv:2410.21724 (2024). Independent researcher, Raasepori, Finland Email address:mikko.fischer@gmail.com

arXiv 2024

Pith tools

Reviewed July 30, 2026 · model on record in the stance chip above.

[1] [1]

Davila, B

R. Davila, B. Brimkov and R. Pepper,In reverie together: ten years of mathematical discovery with a machine collaborator, preprint, arXiv:2507.17780 (2025)

arXiv 2025

[2] [2]

Davila and M

R. Davila and M. A. Henning,Zero forcing in claw-free cubic graphs, Bull. Malays. Math. Sci. Soc.43 (2020), 673–688

2020

[3] [3]

C. C. Fast and I. V. Hicks,Effects of vertex degrees on the zero-forcing number and propagation time of a graph, Discrete Appl. Math.250(2018), 215–226

2018

[4] [4]

Schuerger, N

H. Schuerger, N. Warnberg and M. Young,Zero forcing and vertex independence number on cubic and subcubic graphs, preprint, arXiv:2410.21724 (2024). Independent researcher, Raasepori, Finland Email address:mikko.fischer@gmail.com

arXiv 2024