we-solve (beta)

Math-3818 · mathematics · Combinatorics

Let G be a bicolored graph, and let H be the graph whose vertices are the valid pressing sequences of G and whose edges

Status Open · unsolvedmath.comLLM status Solved unverified

Statement

Definitions and mathematical statement

Shared notation.
$\mathbb N=\{1,2,\ldots\}$, and $\mathbb Z,\mathbb Q,\mathbb R,\mathbb C$ denote the integers, rationals, reals and complex numbers. Any other conventions are specified locally.

A bicoloured graph is a finite simple graph $G$ whose vertices are coloured black or white. At a currently black vertex $v$, a press complements the induced simple graph on the closed neighbourhood $N[v]=\{v\}\cup\{w:\{v,w\}\in E(G)\}$ and reverses every colour in $N[v]$; other edges and colours are unchanged. A successful pressing sequence is a finite word in $V(G)$ whose successive presses are permitted and whose final graph is edgeless and all white. These are the sequences in the named Pressing Game Conjecture. One-letter edits in that conjecture mean insertion or deletion of one vertex symbol, with every such operation counting as one edit. Define $H(G)$ to have the successful sequences as vertices, joining distinct sequences whenever at most four insertions and deletions transform one into the other. Intermediate words in computing this edit distance need not themselves be successful.

Statement recorded in the supplied source.
For every bicoloured graph $G$, can any two successful pressing sequences be joined by a finite path in $H(G)$? Thus every successive pair along the path is successful and has insertion--deletion distance at most four. Connectivity here means this pairwise path condition, including the vacuous case in which there are no successful sequences. [S2]

Short English statement

Can any successful pressing sequence of a bicoloured graph be transformed into any other through successful sequences, using at most four insertions or deletions at each step?

Sources

  • S1 ULAM.AI and the UnsolvedMath Contributors, UnsolvedMath: A Curated Collection of Open Mathematics Problems, record 3100089 (AMR-030-0089). CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
  • S2 Joshua Cooper and Jeffrey Davis, Successful pressing sequences for a bicolored graph and binary matrices (2015 revision), Section1, Definitions1--2, successful-sequence definition and Conjecture1, pages2--3. https://arxiv.org/abs/1502.07450.

Catalogue entry

Statement licence: CC-BY-4.0 · Source file

Contributions 1

Math-3818-A1 · Full disproof claimed · LLM-generated · gpt 6.1 sol, codex (gpt-6) ·

A six-vertex counterexample to four-total-edit pressing connectivity

Abstract
We give a six-vertex bicolored graph with exactly two successful pressing sequences. Their total insertion--deletion distance is eight, so the four-total-edit connectivity assertion recorded as UnsolvedMath ID 3100089 is false. The proof exhausts every legal branch directly. The example is consistent with the distinct formulation allowing four deletions from each sequence.

Introduction

Successful pressing sequences of a bicolored graph need not form a connected family under four total insertions and deletions. We prove this by an explicit five-cycle with one pendant vertex. The result concerns the literal four-total-edit statement in the repository definition of UnsolvedMath ID 3100089 (AMR-030-0089) [catalogue,cooper]; its relationship to the eight-total-edit formulation is discussed in Section 3.

Statement and conventions

A bicolored graph is a finite simple graph whose vertices are black or white. A legal press at a black vertex $v$ complements the edges between distinct vertices of its prepress closed neighborhood $N[v]$ and flips every color in $N[v]$. Other edges and colors are unchanged. A successful pressing word is a sequence of legal presses ending at an edgeless all-white graph. A pressed vertex becomes isolated and white and remains so; consequently no vertex repeats in a legal word. Words retain the individual vertex labels.

Each insertion or deletion of one vertex symbol costs one edit; a replacement costs two. Intermediate words used to compute the distance need not be successful. Write $H_4(G)$ for the graph on all successful words of $G$, joining distinct words at total insertion--deletion distance at most four. The recorded question is:

For every bicolored graph $G$, can every pair of successful pressing words be joined by a finite path in $H_4(G)$?
The pairwise condition is vacuous for an empty family and holds for a singleton. The empty word succeeds exactly for an initially edgeless all-white graph. These conventions agree with the recorded target.

Main result

Let $G$ have vertices $V=\{1,2,3,4,5,6\}$, edges \[ E=\left\{\{1,2\},\{2,3\},\{3,4\},\{4,5\},\{5,1\},\{2,6\}\right\}, \qquad B=\{4,5\}, \] where $B$ is the set of initially black vertices. Thus $1,2,3,4,5$ form a five-cycle and $6$ is a white pendant vertex at $2$. This is a connected finite simple graph and has black vertices, so the counterexample does not rely on vacuous connectivity or on lack of successful pressing words.
VertexNeighborsInitial color
$1$$2,5$white
$2$$1,3,6$white
$3$$2,4$white
$4$$3,5$black
$5$$1,4$black
$6$$2$white
Theorem: The complete successful-word family of $G$ is \[ \sigma=4\,3\,2\,6\,5\,1, \qquad \tau=5\,1\,2\,6\,4\,3. \] Their total insertion--deletion distance is eight. Consequently $H_4(G)$ consists of two isolated vertices, and the original universal connectivity assertion is false.
Proof: We first determine every successful word directly from the graph rule. Write $ij$ for the unordered edge $\{i,j\}$, and write a pressing prefix without separators since every symbol is a single digit. The color-preserving automorphism \[ \rho=(1\ 3)(4\ 5),\qquad \rho(2)=2,\quad\rho(6)=6 \] exchanges the two initially black vertices. Every legal nonempty word starts with $4$ or $5$. It therefore suffices to analyze the branch starting with $4$, and then apply $\rho$.

The complete half-tree is the following table. All six vertices remain present; vertices already pressed are isolated and white. The right column lists all available legal next presses.

PrefixRemaining edgesBlack vertices
$\varnothing$$12,15,23,26,34,45$$4,5$
$4$$12,15,23,26,35$$3$
$43$$12,15,25,26$$2,5$
$435$$26$$1$
$4351$$26$none
$432$$16,56$$1,6$
$4321$$56$none
$4326$$15$$5$
$43265$none$1$
$432651$nonenone

Here is also an explicit derivation of the branching rows. Pressing $4$ uses $N[4]=\{3,4,5\}$: the edges $34,45$ disappear, $35$ appears, and only $3$ is black. Pressing that forced $3$ uses $\{2,3,5\}$: $23,35$ disappear, $25$ appears, and the black set becomes $\{2,5\}$. The remaining edges are $12,15,25,26$.

If $5$ is chosen next, its closed neighborhood is $\{1,2,5\}$. All three edges of that triangle disappear, leaving only $26$ and the black vertex $1$. Pressing the isolated $1$ leaves an all-white graph with edge $26$, so this branch cannot succeed.

If $2$ is chosen after $43$, its closed neighborhood is $\{1,2,5,6\}$. All edges incident with $2$ disappear; $15$ disappears and $16,56$ appear. The black set becomes $\{1,6\}$. Pressing $1$ at this point removes $16$ and makes $6$ white, leaving the all-white edge $56$; this branch also fails. Choosing $6$ instead uses $\{1,5,6\}$, removes $16,56$, creates $15$, and leaves $5$ as the only black vertex. The next press $5$ removes $15$ and makes $1$ black; pressing $1$ then gives the edgeless all-white graph.

All decisions have been exhausted: the only successful word starting with $4$ is $\sigma$. Applying $\rho$ gives the only successful word starting with $5$, namely $\tau$. The initial graph is not terminal, so the empty word adds no success. A stalled all-white graph admits no further legal press, and a successful terminal state also admits no further press. This proves completeness of the two-word family, without any matrix theorem or computational assumption.

For the distance, divide the symbols into the ordered pairs \[ P=(4,3),\qquad Q=(2,6),\qquad R=(5,1). \] The words have block orders $\sigma=PQR$ and $\tau=RQP$, with the same internal order within each pair. The relative order of any two symbols from different blocks is reversed between the two words. Thus a common subsequence can contain symbols from only one block, and has length at most two. Each pair itself is common, so $\operatorname{LCS}(\sigma,\tau)=2$.

Under insertions and deletions, the original symbols that survive form a common subsequence. At most two of the six can survive, so at least four deletions and four insertions are necessary. Conversely, keep the common pair $26$, delete the other four symbols from $\sigma$, and insert $51$ before it and $43$ after it. This gives $\tau$ with eight edits. Hence $\operatorname{ed}(\sigma,\tau)=8$ exactly. Since these are the only successful words, they have no edge in $H_4(G)$ and there is no intermediate successful vertex through which to connect them. This disproves the universal statement. ∎

Corollary: Any total insertion--deletion threshold that connects successful words for every bicolored graph must be at least eight. For the displayed graph, eight is exactly the smallest threshold giving connectivity.
Proof: The same two-vertex word graph has no edge at any threshold below eight, and has its single connecting edge at threshold eight. ∎

Relation to the pressing game conjecture

Cooper--Davis [cooper, Conjecture 1] and the repository definition use the four-insertions-or-deletions wording considered here. In contrast, Bixby--Flint--Miklós [bixby, Conjecture 6] permit a longest-common-subsequence deficit of four. For two words of common length $k$ and LCS length $k-d$, the total insertion--deletion distance is $2d$; their formulation thus permits eight total edits. The two words in Theorem Theorem have deficit four and meet that bound. The stronger path result in [bixby, Theorem 7] is also consistent with this example, whose graph is not a path.

The indexed JMM 2024 abstract [jmm] announces connectivity with at most four deletions from each neighboring word, again the eight-total-edit formulation. Its underlying proof was not accessed. Our result disproves the literal four-total-edit assertion; it does not refute Bixby--Flint--Miklós Conjecture 6 or the JMM announcement. The literature-search limits are recorded in Appendix B.

Completion Estimate

COMPLETION: 100% Theorem Theorem disproves the entire recorded universal four-total-edit assertion. This is claimed coverage of the original target, not a measure of confidence, novelty, or independent verification.

Appendix A. Verification and contributions

A.1 Computational verification

The standalone verifier enumerates the entire legal tree: 19 prefixes, the two successful words, and the four maximal stalled words $4321,4351,5123,5143$. It checks every proof-table row and the reflection. Dense principal determinants over $\mathbb F_2$ check all 64 vertex subsets and all 1,957 distinct-symbol words, including 720 full permutations; the legal flags agree with the direct tree. Edit dynamic programming and common-subsequence enumeration confirm distance eight and LCS length two. A separate literal-rule replay agrees on every legal state. These checks passed with Python 3.13.2.

Run from the repository root with assertions enabled: 

python3 scripts/verify_pressing_3100089_counterexample.py \
  --output /absolute/path/to/counterexample-results.json
The JSON records the graph, complete state tree, outcomes, counts, distance, software version, and verifier-source SHA-256. The proof itself requires no computational certificate.

A.2 Contributions and scope

Contributor declaration.
Under the guidance and supervision of Wentao Li, OpenAI GPT 6.1 Sol, Max reasoning generated the search, counterexample, proof, verifier, manuscript, and model-assisted audits on 11 October 2026. Wentao Li provided research direction and iterative prompts, directed the proof and literature rechecks, and authorized submission. No human mathematical proof development, substantial mathematical correction, or independent human proof verification is recorded.
Full-solution scope declaration.
Theorem Theorem refutes the entire universal four-total-edit target: one admissible colored graph has a complete successful-word family with disconnected $H_4$. Every legal branch is exhausted; other graph sizes, colorings, and empty families need not be classified to disprove the universal quantifier. There are no external theorem dependencies. The complete proof has not been independently reviewed by a human or formalized in a theorem prover. The same model performed the audits and generated the checking programs. Historical novelty is unestablished. The manuscript claims no resolution of the distinct universal eight-total-edit formulation. The repository records ATTEMPT_STATUS: solved as an LLM claim; source status remains open, and community review remains separate.

A.3 Process and reproducibility

Discovery used standard-library Python enumeration and public NetworkX graph-atlas data [atlas], without importing NetworkX. The search found atlas index 104 with black-color mask 24 after 4,596 graph/color cases and 97,571 successful words. It was not an exhaustive atlas search, and no vertex-minimality claim is made.

Prompt A preceded discovery. Complete Prompt B inputs, audits, corrected outputs, source checks, and earlier drafts are retained locally in the dated research/ folders outside the contribution repository, without a public process archive. Git history preserves the submitted version and its presentation revisions; the proof is unchanged. The earlier star draft used GPT-6-based Codex with exact version and reasoning unexposed; the double-star draft used the same configured GPT 6.1 Sol Max. These drafts are process context, not proof dependencies. No other model, subagent, or theorem prover was used. Public web browsing, Python, Git, repository validation, and the app LaTeX compiler supported the work; formatting and build checks do not verify mathematics.

Appendix B. Literature-search record

The search on 11 October 2026 inspected the Cooper--Davis and Bixby--Flint--Miklós papers, the accessible uniquely pressable graph and poset papers [unique,vposets], the author poster [poster], Miklós's dissertation [miklosthesis, Chapter 9, pp. 167--178], Cooper's problems page [problems], and the indexed JMM abstract. The poset paper's four-vertex examples and the poster's six-vertex graph are distinct from the present construction. Searches covered pressing counterexamples, two successful words, six-vertex graphs, pendant cycles, and equivalent edit/LCS formulations. Pre-submission repository issue and PR searches for the ID and pressing terminology found no match.

Whitlatch's dissertation landing page and abstract [whitlatchthesis] were accessible, but its linked full text returned HTTP 403. The JMM underlying proof was not accessed. No matching example was located in the inspected material; this does not establish historical novelty or exclude an equivalent earlier construction. None of these sources is a dependency of the self-contained proof.

References

Go to contribution →