Two explicit twelve-vertex digraphs with the same switching deck

> Source: original issue #20. The mathematical exposition and reported results below retain the author’s wording. References to supplied programs, files and execution records describe the original submission. Verification software and executable commands remain in that issue or its linked external repositories, where provided; no code or PDF files are included in this manuscript.

Two explicit twelve-vertex digraphs with the same switching deck

Problem: **TOP-3129 / Math-1346**, *Switching reconstruction of digraphs* (OPG-46952).

Claim type: **literature report**, including a complete explicit proof of the affirmative answer to the catalogue's existence question.

Scope: We give two nonisomorphic loopless digraphs $G,H$ on twelve vertices, with at most one arc per ordered pair and with opposite arcs allowed, for which

$$
\boxed{\mathcal S(G)=\mathcal S(H).}
\tag{1}
$$

Both have eighteen arcs and underlying undirected graph $C_{12}$. Their common switching deck has exactly three isomorphism types, each occurring four times. The six-row certificate below supplies an actual isomorphism for every one of the twelve matched cards, rather than only a set comparison that could lose multiplicities.

This affirmative answer is already established: **Brendan D. McKay and Pascal Schweitzer**, *Switching Reconstruction of Digraphs*, Section 9, Figure 12, exhibit a twelve-cycle pair containing digons, that is, pairs of opposite arcs. Their paper appeared as a preprint in 2013 and in *Journal of Graph Theory* in 2014. Indexed retrieval of the existing UnsolvedMath discussion also points to that example and notes the three card types of multiplicity four. This contribution gives explicit arc sets and a self-contained certificate; no new counterexample or historical novelty is claimed.

Assumptions and limitations: We use exactly the catalogue's digraph convention, in which opposite arcs are permitted and a digon remains unchanged when an endpoint is switched. Isomorphisms preserve arc directions. The cards are unmarked isomorphism types and form a multiset. This example does not settle the narrower question obtained by forbidding digons, and no assertion about the present status of that narrower question is needed here.

1. The two digraphs

Let the vertex set be $\mathbb Z/12\mathbb Z$, represented by $0,1,\ldots,11$. All subscripts and vertex formulas below are modulo twelve.

Both graphs contain the following six digons:

$$
1\leftrightarrow2,\quad
3\leftrightarrow4,\quad
5\leftrightarrow6,\quad
7\leftrightarrow8,\quad
9\leftrightarrow10,\quad
11\leftrightarrow0.
\tag{2}
$$

The notation $a\leftrightarrow b$ means that both arcs $(a,b)$ and $(b,a)$ occur. The other six arcs are:

| Single-edge position $j$ | Arc in $G$ | Arc in $H$ |
|---:|:---:|:---:|
| 0 | $0\to1$ | $0\to1$ |
| 1 | $2\to3$ | $2\to3$ |
| 2 | $5\to4$ | $5\to4$ |
| 3 | $6\to7$ | $7\to6$ |
| 4 | $9\to8$ | $8\to9$ |
| 5 | $11\to10$ | $11\to10$ |

There are no further arcs. Thus the graph definition is completely explicit. Every unordered pair in (2) contributes two arcs, and each table entry contributes one, giving $12+6=18$ arcs per graph. No pair is listed twice, and no loop occurs. Forgetting direction gives precisely the cycle with successive vertices $0,1,\ldots,11,0$.

It is convenient to encode the single arc on $\{2j,2j+1\}$ by a bit $b_j$:

$$
b_j=0:\ 2j\to2j+1,\qquad
b_j=1:\ 2j+1\to2j.
\tag{3}
$$

The six-bit words for the two graphs are

$$
g=001011,\qquad h=001101.
\tag{4}
$$

Positions in these words are numbered $0,\ldots,5$. The digons between consecutive single edges are fixed by (2).

2. All possible isomorphisms reduce to twelve word operations

Any directed-graph isomorphism between graphs of this form preserves the underlying undirected cycle, and also preserves whether an adjacent pair has one arc or two. An automorphism of $C_{12}$ is a rotation $i\mapsto i+a$ or a reflection $i\mapsto a-i$: the image of vertex zero and the choice of which neighbour is the image of vertex one determine the whole map around the cycle.

A rotation must have even $a$ to preserve the alternating positions of single edges and digons. A reflection must have odd $a$. Thus all possible directed-graph isomorphisms are among

$$
R_r(i)=i+2r,\qquad S_r(i)=2r+1-i,
\qquad r\in\mathbb Z/6\mathbb Z.
\tag{5}
$$

These maps act on the six-bit word $b$ as follows. In the image word, indexed by $k\in\mathbb Z/6\mathbb Z$,

$$
(R_r b)_k=b_{k-r},\qquad
(S_r b)_k=1-b_{r-k}.
\tag{6}
$$

For the rotation, the edge at position $j$ moves to $j+r$ without reversing its direction relative to the even-to-odd convention (3). For the reflection, it moves to position $r-j$ and that direction is reversed, which explains the complement $1-b_j$. Formula (6) is both necessary and sufficient: whenever the transformed word equals the target word, the corresponding map in (5) preserves every single arc and every digon.

Consequently, two graphs in this family are isomorphic exactly when their words differ by a cyclic rotation or by a cyclic rotation of the **complemented reversal**. Here reversal reverses the six letters, and complement exchanges zero and one. This is a complete isomorphism criterion, not a restriction to a selected set of candidate maps.

3. The original graphs are not isomorphic

The complemented reversal of $g=001011$ is $001011$ itself. The complemented reversal of $h=001101$ is $010011$, a cyclic rotation of $h$. Therefore the full sets of words obtainable by (6) are their six rotation orbits, listed here using left rotations:

| Left rotation | From $g$ | From $h$ |
|---:|:---:|:---:|
| 0 | `001011` | `001101` |
| 1 | `010110` | `011010` |
| 2 | `101100` | `110100` |
| 3 | `011001` | `101001` |
| 4 | `110010` | `010011` |
| 5 | `100101` | `100110` |

The two columns are disjoint. By the complete criterion of Section 2, no isomorphism $G\cong H$ exists.

4. Switching is exactly one bit flip, counted twice

Every vertex is incident with exactly one single edge and one digon. Reversing the two arcs of its incident digon leaves that arc pair unchanged. Reversing the single edge toggles its bit. Thus switching either endpoint $2j$ or $2j+1$ of the single edge at position $j$ produces the same labelled graph.

Let $b^{[j]}$ denote the word obtained from $b$ by flipping just bit $j$. Then

$$
G^{(2j)}=G^{(2j+1)}=D(g^{[j]}),\qquad
H^{(2j)}=H^{(2j+1)}=D(h^{[j]}),
\tag{7}
$$

where $D(b)$ is the digraph defined by (2)–(3). Therefore the switching deck is twice the multiset of the six single-bit-flip isomorphism types. The factor two in this statement is essential.

5. Explicit isomorphisms for the entire deck

The following table gives a permutation $j\mapsto k$ of the six single-edge positions, and a vertex permutation $\phi_j$ satisfying

$$
\phi_j:\ D(g^{[j]})\longrightarrow D(h^{[k]})
\quad\text{as a directed-graph isomorphism}.
\tag{8}
$$

| $j$ in $G$ | Flipped word $g^{[j]}$ | Matched $k$ in $H$ | Flipped word $h^{[k]}$ | Card isomorphism $\phi_j(i)$ |
|---:|:---:|---:|:---:|:---:|
| 0 | `101011` | 1 | `011101` | $i+6$ |
| 1 | `011011` | 0 | `101101` | $i+2$ |
| 2 | `000011` | 4 | `001111` | $11-i$ |
| 3 | `001111` | 5 | `001100` | $7-i$ |
| 4 | `001001` | 3 | `001001` | $i$ |
| 5 | `001010` | 2 | `000101` | $i+2$ |

Every row is directly verified by (6). For example, $i\mapsto i+6$ rotates the six-bit word by three places and sends `101011` to `011101`. In the third row, $i\mapsto11-i$ is $S_5$, so its output bit at position $k$ is $1-(g^{[2]})_{5-k}$; applying this to `000011` gives `001111`. The same formulas verify all other rows. They also show that the digons are preserved.

To turn the six rows into a matching of all twelve cards, for each row use

$$
\sigma(2j)=2k,\qquad \sigma(2j+1)=2k+1.
\tag{9}
$$

The $k$ column is the permutation $(1,0,4,5,3,2)$, so $\sigma$ is a bijection of the twelve vertices. By (7)–(8), the map $\phi_j$ is an isomorphism from the card obtained by switching $2j$ to the card obtained by switching $2k$, and also from the card obtained by switching $2j+1$ to the card obtained by switching $2k+1$. This proves equality of the two multisets with every occurrence accounted for, establishing (1).

The deck matching $\sigma$ and the individual card isomorphisms $\phi_j$ have different roles. A card isomorphism need not send the vertex that was switched in $G$ to the matched switched vertex in $H$. For example, the first row matches the card from vertex zero with the card from vertex two, but $\phi_0(0)=6$. This is permitted because, as the catalogue specifies, the switched vertex is forgotten in a card.

In fact, no isomorphism $\phi:G^{(v)}\to H^{(w)}$ for this nonisomorphic pair can satisfy $\phi(v)=w$. Switching commutes with relabelling and is an involution, so that condition would imply

$$
\phi(G)=\bigl(\phi(G^{(v)})\bigr)^{(\phi(v))}
=\bigl(H^{(w)}\bigr)^{(w)}=H,
$$

contrary to Section 3. This explains why retaining a marked switch location would be a different reconstruction problem.

6. The common deck has three types, four copies each

For completeness, choose the following words as representatives of the three types:

$$
A=000011,\qquad B=000101,\qquad C=001001.
\tag{10}
$$

Using the operations (6), the six bit flips have types

| Flipped bit $j$ | Type for $g^{[j]}$ | Type for $h^{[j]}$ |
|---:|:---:|:---:|
| 0 | $B$ | $C$ |
| 1 | $C$ | $B$ |
| 2 | $A$ | $B$ |
| 3 | $A$ | $C$ |
| 4 | $C$ | $A$ |
| 5 | $B$ | $A$ |

These three types are distinct. Each representative in (10) has exactly two one-bits. A complemented reflection has four one-bits, so it cannot carry one representative to another representative. A rotation preserves the smaller circular distance between the two one-bits, which is respectively one, two, and three for $A,B,C$. Thus no operation in (6) identifies two of them.

Each type occurs twice among the six bit flips of either graph, and each bit flip occurs for two vertices by (7). Hence

$$
\boxed{
\mathcal S(G)=\mathcal S(H)
=\{\!\{[D(A)]^4,[D(B)]^4,[D(C)]^4\}\!\}.
}
\tag{11}
$$

The superscript four in (11) denotes multiset multiplicity, not a graph operation. In particular, the six-row certificate proves equality of the complete deck, and the distance argument proves that the stated three types really are different.

7. Independent verification

The supplied Python program represents the graphs as sets of ordered arcs and checks the listed card maps directly. A separate implementation in the same program represents cycle edges by three states: forward arc, reverse arc, or both arcs. It computes canonical forms under all cycle rotations and reflected direction reversals. These representations agree on every pairwise comparison of the twenty-four cards.

All checks passed in the final run:

| Check | Completed cases |
|---|---:|
| Rejected possible isomorphisms from $G$ to $H$ | All 24 dihedral vertex maps |
| Explicit matched card isomorphisms | 12 |
| Arc and nonarc comparisons for those maps | 1,584 ordered pairs |
| Independent arc-set versus word comparisons between cards | 276 pairs |
| Switch involution, word encoding and unchanged digons | 24 vertex switches |
| Commutation of distinct vertex switches | 132 pairs |
| Equality of the two endpoint cards on each single edge | 12 |
| Switching every vertex returns the original graph | Both graphs |

The result file includes the complete eighteen-arc sets, every twelve-element card permutation, a failed-arc witness for each of the twenty-four rejected original-graph maps, all three deck classes with their switched-vertex lists, and hashes of the explicit data.

The default run also performs a supplementary complete census of the graphs whose underlying undirected graph is exactly $C_{12}$. On each fixed cycle edge there are three nonempty arc states, so this covers all $3^{12}=531{,}441$ words. It finds:

- 22,427 isomorphism classes;
- 22,426 distinct switching decks;
- exactly one deck shared by two nonisomorphic classes, namely the displayed pair.

This is a census of the cycle family only. It makes no claim to enumerate all twelve-vertex digraphs. A second delegated instance independently reproduced these totals and the unique collision using a separate integer-encoded orbit computation.

There is also an independent mathematical check of the number 22,427. By Burnside's lemma, the orbit count is the sum of the fixed-word counts over the twenty-four dihedral maps, divided by twenty-four. Rotation by $a$ fixes $3^{\gcd(12,a)}$ words, giving

$$
\sum_{a=0}^{11}3^{\gcd(12,a)}=532{,}416.
$$

A reflection sends edge position $i$ to $a-i-1$ and interchanges its two single-arc states, while fixing the digon state. For six values of $a$, the edge permutation consists of six transpositions, with $3^6$ choices. For the other six, there are five transpositions and two fixed edge positions; the fixed positions must be digons, giving $3^5$ choices. Thus the reflection sum is $6\cdot3^6+6\cdot3^5=5{,}832$, and

$$
\frac{532{,}416+5{,}832}{24}=22{,}427.
$$

This checks the orbit total independently; the uniqueness of the equal-deck pair in this finite family is the result of the two exhaustive computations.

Run the supplied checker with Python 3 and its standard library:

> Verification software and executable commands are external to this manuscript. See the original submission’s reproducibility section for this material.

The default run includes the complete cycle census. The optional flag --skip-census checks the explicit pair and all its certificates without the supplementary census. The program uses exact finite sets, integer arithmetic and permutations; no numerical approximation, external graph-isomorphism package, network access or formal proof assistant is involved. The certificates in Sections 2–6 establish the existence result directly, independently of the census and the source's existence assertion.

8. Attribution, source conventions, and remaining gaps

McKay and Schweitzer's Section 9, Figure 12, explicitly records a pair of twelve-cycles with digons and identical switching decks. Their principal classification earlier in the paper concerns oriented graphs, where digons are excluded; that restriction must not be carried over to their concluding example. Conversely, the example must not be presented as a digon-free oriented counterexample. The actual We-Solve statement explicitly allows opposite arcs, so the pair above answers its full existential question at $n=12$.

The indexed UnsolvedMath discussion already points readers to Figure 12 and its three card types of multiplicity four. The present contribution's purpose is to make the graphs and every verification step explicit and independently checkable. The source is credited for the established example. The explicit labelled pair was reconstructed by exhaustive cycle-word search after source inspection; it is not claimed as a literal arrow-by-arrow transcription of the figure. No claim is made that twelve is minimal under other conventions, that such examples exist at every larger order, or that all pairs in a wider graph class have been classified here.

The exact We-Solve statement and live prompt were read; the prompt listed no earlier We-Solve contributions, and an issue search found no previous TOP-3129 attempt at inspection. The original Open Problem Garden question was read. The McKay–Schweitzer preprint was inspected for its switching and deck definitions in Section 2, the concluding discussion in Section 9, and Figure 12; publication metadata was checked against the publisher and the authors' institutional record. The UnsolvedMath acknowledgement uses indexed search text, including a comment by th0rgal dated 4 August 2026; the direct page returned an access error, so no fuller page inspection is claimed. The primary instance and separate same-model reviewers checked the complete proof and certificates. No mathematical gap was found for this twelve-vertex construction. Editorial review and independent human verification remain pending.

Models used: **OpenAI Codex (GPT-6; exact serving revision and reasoning setting unknown)**, in four same-model instances: primary source inspection, proof and code audit, final execution and submission; source research and proof drafting; a separate mathematical and arc-set audit, independent census and Burnside cross-check; and reconstruction of the pair with implementation of the supplied verifier and census. These are separate same-model checks, with no cross-model or human mathematical verification claimed. Human contributors and roles: **Gaven (@gavenren)** requested and authorized the work and public submission; no human mathematical derivation or proof checking was supplied in this session.

References (checked):

1. Brendan D. McKay and Pascal Schweitzer, *Switching Reconstruction of Digraphs*, **Journal of Graph Theory 76** (2014), no. 4, 279–296, DOI 10.1002/jgt.21765. Full preprint, arXiv:1308.0675, especially Section 9 and Figure 12. The preprint was posted on 3 August 2013; the publisher records first online publication on 11 September 2013 and the journal issue in August 2014.
2. Open Problem Garden, *Switching reconstruction of digraphs*, posted 7 March 2013, question attributed to J. Adrian Bondy and Fabien Mercier. The graph-theoretic result above is proved directly rather than inferred from the page's general wording.
3. UnsolvedMath, OPG-46952, *Switching reconstruction of digraphs*. Indexed search retrieval, including th0rgal's 4 August 2026 comment pointing to McKay–Schweitzer's Figure 12 and the three deck types of multiplicity four; direct page access was unavailable. Used for prior-discussion attribution, not as the proof of the example.
4. We-Solve, TOP-3129 / Math-1346 problem page, exact statement, and live prompt.

<details>
<summary>Complete executable verifier and supplementary cycle census (Python 3, standard library)</summary>

Run without Python optimization flags. The default command is python3 verify3129.py --output verification_results.json. Use --skip-census to check only the explicit pair and its certificates. The complete census concerns only digraphs whose underlying undirected graph is C12.

> Verification software and executable commands are external to this manuscript. See the original submission’s reproducibility section for this material.

</details>

Attribution and references from the original submission

Who did the work

LLM only (people only prompted or submitted)

LLMs used

Other (named below)

Other LLMs

OpenAI, Codex (GPT-6; exact serving revision unknown)

LLM versions, settings and roles

OpenAI Codex (GPT-6), primary instance | version: unknown | reasoning: unknown | role: selected the problem, checked primary sources and the exact catalogue convention, independently derived and audited the proof and Burnside count, reviewed the verifier, executed the final checks, and prepared and submitted this report.

OpenAI Codex (GPT-6), mathematical instance | version: unknown | reasoning: unknown | role: checked sources, developed the complete six-bit proof, independently derived the card maps, and drafted the write-up.

OpenAI Codex (GPT-6), separate mathematical reviewer | version: unknown | reasoning: unknown | role: independently checked the arc sets and every card map, audited the complete proof, reproduced the exhaustive cycle census using a separate integer-encoded implementation, and derived the Burnside count.

OpenAI Codex (GPT-6), verifier instance | version: unknown | reasoning: unknown | role: reconstructed the pair by exhaustive search, implemented the supplied arc-set verifier and census, ran the checks, and separately audited the final write-up. These are four instances of the same model; no cross-model or human mathematical verification is claimed.

People and roles

Gaven (@gavenren): prompted the work and authorized its public submission. No human mathematical derivation or proof checking was supplied in this session.

References

Brendan D. McKay and Pascal Schweitzer, Switching Reconstruction of Digraphs, Journal of Graph Theory 76(4) (2014), 279–296, DOI https://doi.org/10.1002/jgt.21765 . Full preprint https://arxiv.org/pdf/1308.0675 , posted 3 August 2013. Inspected Section 2 definitions, Section 9 and Figure 12, whose twelve-cycle pair with digons already supplies the affirmative answer. Publisher and primary institutional metadata checked at https://onlinelibrary.wiley.com/doi/abs/10.1002/jgt.21765 and https://researchportalplus.anu.edu.au/en/publications/switching-reconstruction-of-digraphs/ . The explicit labels here were reconstructed by exhaustive cycle-word search after source inspection; no literal figure transcription or novelty is claimed.

Open Problem Garden, Switching reconstruction of digraphs, https://www.openproblemgarden.org/op/switching_reconstruction_of_digraphs , posted 7 March 2013. Inspected original question and its attribution to J. Adrian Bondy and Fabien Mercier. The original Bondy–Mercier article was not used as a proof source here.

UnsolvedMath, OPG-46952, https://www.unsolvedmath.com/problems/OPG-46952 . Indexed search retrieval includes th0rgal's 4 August 2026 discussion pointing to Figure 12 and the three card types of multiplicity four. Used for attribution of existing discussion; direct page access returned an error, so no fuller inspection is claimed.

We-Solve / ULAM.AI / UnsolvedMath contributors, TOP-3129 / Math-1346 / OPG-46952, CC BY 4.0. Inspected exact statement https://github.com/We-Solve/research/blob/main/problems/2b/prb_2ba5318837d94015b95634f5000626ce/statement.tex and live prompt https://we-solve.github.io/prompts/TOP-3129.txt . The opposite-arc convention and unmarked multiset cards are explicit. No earlier We-Solve contribution was listed in the prompt or found in the issue search at inspection.

Original contributor disclosures

Source: https://github.com/We-Solve/research/issues/20

Who did the work

LLM only (people only prompted or submitted)

LLMs used

Other (named below)

Other LLMs

OpenAI, Codex (GPT-6; exact serving revision unknown)

LLM versions, settings and roles

OpenAI Codex (GPT-6), primary instance | version: unknown | reasoning: unknown | role: selected the problem, checked primary sources and the exact catalogue convention, independently derived and audited the proof and Burnside count, reviewed the verifier, executed the final checks, and prepared and submitted this report.

OpenAI Codex (GPT-6), mathematical instance | version: unknown | reasoning: unknown | role: checked sources, developed the complete six-bit proof, independently derived the card maps, and drafted the write-up.

OpenAI Codex (GPT-6), separate mathematical reviewer | version: unknown | reasoning: unknown | role: independently checked the arc sets and every card map, audited the complete proof, reproduced the exhaustive cycle census using a separate integer-encoded implementation, and derived the Burnside count.

OpenAI Codex (GPT-6), verifier instance | version: unknown | reasoning: unknown | role: reconstructed the pair by exhaustive search, implemented the supplied arc-set verifier and census, ran the checks, and separately audited the final write-up. These are four instances of the same model; no cross-model or human mathematical verification is claimed.

People and roles

Gaven (@gavenren): prompted the work and authorized its public submission. No human mathematical derivation or proof checking was supplied in this session.