Counterexample to Written on the Wall II Conjecture 291

## Summary

Written on the Wall II Conjecture 291 is false.

The currently formalized conjecture states that every finite simple connected graph $G$ with more than two vertices satisfies

$$
\gamma_t(G) \le k(G) + \mathrm{freq}(t_{\min}),
$$

where $\gamma_t$ is the total domination number, $k$ is the first Havel–Hakimi iteration at which a zero appears, and $\mathrm{freq}(t_{\min})$ is the number of vertices attaining the minimum incident-triangle count.

I found the following infinite counterexample family. It also disproves the source statement without the extra order hypothesis discussed in #4509.

## Construction

For every integer $m \ge 6$, let $G_m$ have vertices

$$
a,b,x_1,\ldots,x_m,p,q,r,\ell.
$$

Add exactly these edges:

- $ab$;
- $ax_i$ and $bx_i$ for every $1 \le i \le m$;
- $px_1$ and $pb$;
- $qx_1$, $qa$, and $q\ell$;
- $x_2x_3$, $rx_2$, and $rx_3$.

Thus the base is a book graph with $m$ triangular pages, together with four additional vertices. The smallest member in this family, $G_6$, has 12 vertices and 21 edges.

## Invariants

For every $m \ge 6$,

$$
\gamma_t(G_m)=4,\qquad k(G_m)=2,\qquad
\mathrm{freq}(t_{\min})=1.
$$

### Triangle frequency

The leaf $\ell$ is contained in no triangle. Every other vertex is contained in at least one triangle: $p,b,x_1$ form a triangle; $q,a,x_1$ form a triangle; $r,x_2,x_3$ form a triangle; and every $x_i$ belongs to the triangle $a,b,x_i$. Hence $\ell$ is the unique vertex attaining the minimum triangle count, so $\mathrm{freq}(t_{\min})=1$.

### Havel–Hakimi zero step

The descending degree sequence is

$$
[m+2,m+2,4,4,4,3,2^{(m-1)},1].
$$

No zero occurs initially or after the first Havel–Hakimi step. After two steps the sequence is

$$
[2,2,2,1,1,1,1,1,1,0^{(m-5)}],
$$

so the first zero occurs at step $2$.

### Total domination number

The set $\{q,a,x_1,x_2\}$ is a total dominating set, so $\gamma_t(G_m)\le4$.

Conversely, every total dominating set must contain $q$, because $\ell$ is a leaf. It must also contain a neighbor of $q$, a neighbor of $p$, and a neighbor of $r$. Since

$$
N(p)=\{b,x_1\},\qquad N(r)=\{x_2,x_3\},
$$

these last two requirements need two distinct vertices. If a three-vertex total dominating set existed, its two vertices besides $q$ would therefore have to include one vertex from each of these two disjoint sets. To dominate $q$, the first choice must be $x_1$, because $x_1$ is the only member of $N(p)\cup N(r)$ adjacent to $q$. The resulting set would be either $\{q,x_1,x_2\}$ or $\{q,x_1,x_3\}$, but then $x_4$, whose neighborhood is $\{a,b\}$, would be undominated. Thus no three-vertex total dominating set exists, and $\gamma_t(G_m)=4$.

Therefore the conjectured inequality becomes

$$
4 \le 2+1=3,
$$

which is false.

## Verification and scope

For $G_6$, I exhaustively enumerated all vertex subsets to check total domination and directly computed all vertex triangle counts and Havel–Hakimi iterations. The formulas above establish the same invariants for every $m\ge6$.

A follow-up pull request will provide a Lean certificate against the repository's exact definitions and mark Conjecture 291 as false/solved. I am not claiming that $G_6$ is globally minimal or that worldwide historical priority has been established.

## AI assistance disclosure

OpenAI Codex assisted with the counterexample search, mathematical derivation, independent finite verification, and write-up. The construction and calculations should receive normal independent and formal review.

## Planned contribution

- [x] I plan to submit the follow-up pull request.
- [ ] This issue is up for grabs.

Start by locating the repository's exact definitions for total domination, the Havel–Hakimi invariant, triangle frequency, and Conjecture 291. Formalize the stated G₆ counterexample and verify the three invariants against those definitions, then prepare the planned certificate and mark the conjecture false or solved.

Written by the indexing model from the issue text.