--- title: "A 48-vertex cubic counterexample to independent domination versus minimum maximal matching" date: 2026-08-24 version: "0.1.0-candidate" doi: 10.5281/zenodo.22083656 pdf: https://github.com/ipitchford/txgraffiti-order48-successor/releases/download/v0.1.0-candidate/txgraffiti_order48_successor_MANUSCRIPT_v0.1.0_candidate.pdf repository: https://github.com/ipitchford/txgraffiti-order48-successor archive: https://zenodo.org/records/22083656 license: CC0-1.0 status: unrefereed (internally replayed; not peer reviewed, not independently reproduced, not formally verified) --- # A 48-vertex cubic counterexample to independent domination versus minimum maximal matching ## Summary This release supplies one explicit connected cubic graph $G$ on 48 vertices for which $$ \mu^*(G)=15<16=i(G). $$ Here $\mu^*(G)$ is the minimum size of a maximal matching and $i(G)$ is the minimum size of an independent dominating set. The strict inequality makes this graph a counterexample to the proposed bound $i(G)\leq\mu^*(G)$ for regular graphs. The earlier public Evidence Press candidate used 50 vertices. This child release lowers the known candidate-order upper bound to 48. It does **not** prove that 48 is the smallest possible order or that this graph is the only example at that order. > **Candidate status:** Anonymous · unrefereed · explicit finite graph theorem · bundled deterministic replay passed · independent reconstruction, external specialist review, formal verification and editorial peer review not assessed. ## Exact result for specialists The canonical graph is finite, simple, connected and cubic, with 48 vertices and 72 edges. The package gives a 15-edge maximal matching. Conversely, every maximal matching in a cubic graph edge-dominates the graph, and one matching edge is incident with at most five distinct edges. Therefore every maximal matching in this graph has at least $$ \left\lceil\frac{72}{5}\right\rceil=15 $$ edges, proving $\mu^*(G)=15$. An explicit independent dominating set has 16 vertices. A separate compressed proof tree excludes every independent dominating set of size at most 15, proving $i(G)=16$. Thus a cubic counterexample exists at order 48 and the minimum counterexample order is at most 48. ## How the certificate works The checker stores a selected independent set $S$ and the vertices dominated by it. At each branch it chooses an undominated witness $w$. Every independent dominating extension must select a legal vertex in the closed neighbourhood $N[w]$, so the checker reconstructs and explores every candidate in $N[w]\setminus N[S]$. A bound leaf is accepted only when the number of already selected vertices plus $\lceil r/4\rceil$ is greater than 15, where $r$ is the number of undominated vertices. The factor four is valid because a vertex in a cubic graph has a closed neighbourhood of size four. The canonical tree contains 437,188 nodes, 201,592 branches and 235,596 bound leaves. The certificate stores branch witnesses rather than trusting stored candidate lists. The C++ generator is then rebuilt from source and must reproduce the normalized gzip certificate byte for byte. This separation is useful, but both programs remain products of one coordinated workflow. ## Evidence, replay and assurance boundary The release cross-checks the JSON, edge-list and graph6 encodings; verifies the explicit matching and independent dominating set; reads the proof tree under ordinary and optimized Python; regenerates the certificate; and rejects eight targeted corruptions, including a bad leaf, invalid branch witness, truncation, trailing data, malformed header, duplicate edge and damaged explicit witnesses. The final archive passes from a clean extraction. GitHub Actions repeats the workflow under Python 3.11 and 3.13. The GitHub prerelease and Zenodo record carry byte-identical copies of the source ZIP, two PDFs, review bundle and checksum ledger. These checks establish availability, integrity and producer-side replay of the encoded finite claim. They do not establish an unaffiliated rerun, an independently authored implementation, end-to-end formal verification, external specialist review or journal peer review. The five-role reports are internal model-mediated quality control over a frozen archive, not independent human review. ## What is inherited and what is new The public parent release presents a 50-vertex cubic counterexample and leaves the unrestricted search below 50 open. The present release supplies a different 48-vertex object, so it is a substantive child result rather than a correction or new version of the parent. The new contribution is the smaller graph, its witnesses, its 437,188-node exclusion certificate and the resulting order-48 upper bound. The child does not retract the parent, and it does not inherit the parent's separate formula-graph identity or conditional threshold theorem for cubic graphs with a dominating induced matching. The 48-vertex graph lies in the non-DIM stratum recorded by the package. Shared problem framing, provenance and certificate architecture make this a genuine research lineage. They also mean that the parent and child are not independent checks of one another. ## What the result does not establish - It does not exclude counterexamples on fewer than 48 vertices. - It does not prove global minimality at order 48 or uniqueness at that order. - It does not establish first discovery, absolute novelty or secured priority. - It does not make the checker independent merely because the generator is separately compiled. - It does not turn internal model-mediated review, CI, hashes, DOI publication or public availability into independent mathematical reproduction. - It does not claim formal verification, external specialist review, editorial peer review or scientific impact. ## Who should care, and why | Reader | Potential use | Principal caution | |---|---|---| | Graph theorists | Inspect a smaller explicit counterexample and test the independent-domination exclusion argument. | The result is an unrefereed candidate and global minimality remains open. | | Exact-computation researchers | Study a compact finite theorem object with a regenerated proof tree and semantic mutation controls. | The implementations share producer-side lineage. | | TxGraffiti users | Update the public candidate-order upper bound from 50 to 48. | The child is separate from the parent's restricted-class theorem. | | Formalization researchers | Use the graph, witnesses and tree grammar as a bounded target for proof-assistant work. | No formalization is included in this release. | | General readers | See how one explicit object plus an exhaustive exclusion certificate can refute a universal inequality. | A public counterexample candidate is not peer-reviewed consensus. | ## How to inspect and reproduce the recorded checks Download the immutable [v0.1.0 candidate release](https://github.com/ipitchford/txgraffiti-order48-successor/releases/tag/v0.1.0-candidate) or the [DOI archive](https://doi.org/10.5281/zenodo.22083656), then verify `SHA256SUMS.txt`. After extracting the candidate ZIP, run: ```sh ./run_core_verification.sh ``` The command requires Python 3.11 or later, a C++20 compiler and `gzip`; no third-party Python package is theorem-critical. It checks all three graph encodings, both explicit witnesses, the proof tree in normal and optimized modes, byte-identical regeneration, eight negative controls, machine-readable claim boundaries and the internal manifest. An independent mathematical audit should reconstruct the graph definitions, the $72/5$ matching lower bound, the branch exhaustiveness and the bound-leaf argument before relying on the supplied implementation. ## The most valuable next projects 1. Run the exact tagged package unaffiliated and publish a byte-bound replay receipt. 2. Write a separate checker from the certificate grammar and compare its verdict on the canonical tree and hostile mutations. 3. Commission a graph-theory specialist review of the matching proof, independent-domination search semantics and source-to-encoding bridge. 4. Perform an independently specified exhaustive or certified search below order 48. 5. Search broader graph databases and literature for equivalent objects while retaining the current no-priority ceiling. ## What is in the public package The repository contains the canonical graph in three encodings, explicit matching and independent-dominating witnesses, compressed proof tree, checker, generator, eight mutation controls, manuscript, evidence supplement, machine-readable claims and assurance, provenance and literature records, internal review reports, licences, deterministic manifest, archive builder and CI workflow. GitHub and Zenodo carry the exact candidate ZIP, manuscript PDF, evidence-supplement PDF, frozen internal-review bundle and checksum ledger. Original prose, structured claims and original data are CC0-1.0; original code is MIT; preserved source inputs retain their existing terms. Evidence Press art, Open Graph media, transcript, audio and thumbnail are communication aids rather than additional mathematical evidence. ## Open directions for follow-up research - Determine whether any cubic counterexample exists on fewer than 48 vertices using an independently specified exhaustive search or lower-bound argument. - Obtain an unaffiliated rerun of the exact tagged package and a separately authored checker for the graph, witnesses and independent-domination exclusion certificate. - Seek external specialist review of the elementary matching argument, proof-tree semantics, source-to-encoding bridge and global scope boundary. - Investigate uniqueness or multiplicity at order 48 without inferring either from the single supplied object. - Clarify novelty and priority through a broader graph-database and literature search while preserving the current no-first-discovery ceiling. ## Research process and reusable methods This is prospective process metadata. It records the intended handoff and claim boundary; it is not evidence that the method accelerated this work. - Work ID: ep-work:txgraffiti-order48-successor - Attempt receipts: ep-attempt:txgraffiti-order48-successor: published / positive; measured-partial; active human minutes missing; compute minutes missing; rework minutes missing; assurance endpoint measured-partial. Work ledger: https://evidencepress.org/api/work-ledger.json - Intended aims: science - Artifact roles: research-output, evidence-assessment, method-demonstration, communication - Decision object: counterexample — An explicit 48-vertex connected cubic graph, matching and independent-dominating witnesses, plus an exhaustive proof-tree certificate establishing mu*(G)=15<16=i(G). Scope: A constructive order-48 counterexample and resulting upper bound on minimum cubic counterexample order; not a lower bound below 48, global minimality, uniqueness or priority. - Reusable methods: Certificate-first, proof-carrying research (certificate-first); Adversarial scientific controls (adversarial-controls); Explicit research-lineage reuse (research-lineage-reuse); Counterexample- and proxy-first analysis (counterexample-proxy-first); Assurance as a vector (assurance-vector); Agent-readable research objects (agent-readable-research-object). Registry: https://evidencepress.org/api/method-registry.json - Targeted clocks: discovery, assurance, publication - Semantic bridge: explicit — The manuscript defines both graph parameters, binds three graph encodings to one labelled object, proves the matching equality by witness and edge count, and specifies how the independent-domination proof tree exhausts all legal extensions before the checker accepts a leaf. Remaining risks: The graph, checker, generator and explanatory proof were integrated in one producer workflow and may share a source-to-semantics error.; The proof tree establishes only the supplied order-48 object theorem; it does not search or exclude all smaller cubic graphs.; The bounded literature audit cannot establish absolute novelty or priority.; No external graph-theory specialist has reconstructed the argument from the immutable package.. - Human judgement gates: Check the graph-parameter definitions, maximal-matching lower bound and proof-tree exhaustiveness as mathematics rather than inferring them from successful execution.; Keep the constructive order-48 upper bound separate from global minimality and uniqueness.; Treat the parent as research lineage and prior public evidence, not independent confirmation of the child.; Require external specialist and broader priority review before first, minimal, unique or definitive language.; Confirm Anonymous scholarly attribution, component licences, immutable identifiers and release authority before publication. - Next assurance action: Obtain an unaffiliated exact-object rerun and separately authored checker, then have a graph-theory specialist assess the proof-tree semantics and commission an independently specified search below order 48. - Claim ceiling: A producer-side anonymous unrefereed certificate-backed candidate proving one explicit order-48 cubic counterexample and an upper bound of 48; not global minimality, uniqueness, independent reproduction, formal verification, external specialist or editorial peer review, absolute priority or demonstrated workflow impact. - Aim-scoped impact evidence: - science: NO_IMPACT_EVIDENCE — Faster or more reliable discovery and assurance of finite graph counterexamples in Certificate-first AI-assisted research on independent domination and minimum maximal matching in cubic graphs; design none; comparator No matched conventional research, theorem-review or publication workflow was registered.; estimand No effect on discovery time, active human effort, compute, error rate, assurance time, reuse, uptake or citation was estimated.; no real-world effect evidence asserted - Parent handoffs: extends-result txgraffiti-c3-resolution; inherited claim: The parent supplies a public 50-vertex candidate counterexample and explicitly leaves the unrestricted below-50 search open. The child supplies a different 48-vertex graph and lowers that upper bound by construction.; inherited ceiling: The parent is an unrefereed producer-side candidate. Shared problem framing, provenance and certificate architecture are dependency evidence, not independent confirmation, and a common defect can propagate across the lineage. ## Verification status Anonymous, unrefereed certificate-backed candidate. The explicit finite graph theorem and order-48 upper bound pass bundled deterministic replay, mutation controls, clean extraction, cross-version CI and cross-archive byte readback. The five-role editorial reports found no unresolved critical, major or minor repair within the frozen package, but they are internal and model-mediated. No unaffiliated rerun, independently authored implementation, formal proof, external graph-theory specialist review, journal peer review, global-minimality proof, uniqueness result or priority determination is reported. The child extends the public 50-vertex release and resolves its below-50 search direction by example; it does not retract the parent or inherit its separate formula-graph and restricted-class theorems. ## Sources and related work - Caro, Y., Davila, R., & Pepper, R. (2021). New results relating independence and matchings. Discussiones Mathematicae Graph Theory, 41, 921-935. - Release contributors. (2026). TxGraffiti Conjecture 15/3 resolution: a certificate-backed candidate counterexample (Version 4.0.0-rc1). - TxGraffiti Conjecture 3 counterexample repository and public predecessor objects.