# Verification report

Manuscript: Non-Word-Representable Single-Triangle Graphs with Word-Representable Line Graphs.
Author: Alper Ferudun, Mercury Software GmbH. Version 1.1, 17 October 2026.

## Accepted scope

For every odd m >= 5, the graph mu(C_m) plus the edge joining shadow vertices 1' and m' is connected, has exactly one triangle, is not word-representable, and has a word-representable line graph. This is a connected strengthening of a 2025 follow-up question. The older GRAPH-049 question was resolved by Mozhui, Dwary and Krishna; it is not a new original-problem closure by this project.

Version 1.1 proves that every member is 4-vertex-critical and therefore induced-minimal non-word-representable. The general added-edge theorem assumes a k-vertex-critical base and k>=3; it constructs a k-coloring after deletion of the apex, a shadow, or an original vertex. This does not assert edge-deletion minimality or minimum order.

## Written verification

The independent-set restriction lemma is proved without assuming false edge-monotonicity. The published odd-Mycielski obstruction of Kitaev and Pyatkin implies non-word-representability of the root graph. The published line-graph orientation of Mozhui, Dwary and Krishna is explicitly retained. Its six relevant boundary vertices are analyzed for all paths, not just edges. The new vertex has five incoming neighbors and one outgoing neighbor, an old sink. Every possible new shortcut is covered by the endpoint/interior cases; the corresponding paths induce transitive cliques. The graph counts and the unique triangle follow directly from the root construction.

The new criticality proof checks all edge types in all three deletion cases. In the original-vertex case, one surviving endpoint of the distinguished edge receives color 0, its shadow also receives 0, other shadows receive k-1, and the apex receives 1. The hypothesis k>=3 separates these shadow and apex colors. In the shadow-deletion case the missing shadow allows its original and the apex to use the extra color. The apex-deletion case copies a base coloring. Three-colorability implies semi-transitive orientability by ordering the colors, so all proper induced subgraphs of G_m are word-representable.

## Exact reproducibility

The C++ program enumerates all 1,048,576 orientations of mu(C_5) and all 2,097,152 orientations of its shadow-edge extension. There are respectively 167,400 and 223,584 acyclic orientations, and zero semi-transitive orientations in both cases. Every acyclic orientation is independently checked by direct path enumeration as well as reachability intervals. Controls K3, C5 and W5 have respectively 6, 20 and 0 semi-transitive orientations.

The Python programs reproduce the cited orientation, inspect all 35 triangle-producing single-edge additions while fixing that orientation, and verify the connected unique-triangle extension at sixteen odd lengths: 5 through 31, then 41 and 51. The first three are cross-checked by literal directed-path enumeration. The excluded m=3 case fails the old-orientation check. The smallest family member has 11 vertices and 21 edges; its line graph has 21 vertices and 61 edges. Failed fixed-orientation extensions are not nonexistence theorems.

The new constructive program verifies 1668 deletion colorings for odd cycles of lengths 5 through 31, then 41, 51, 101, 151 and 201, and for complete bases K3 through K7. A separate exact coloring search checks the eleven-vertex case. The k=2 extension contains a triangle after an original deletion and is rejected; a deliberately corrupted coloring is also rejected. Normal and optimized Python outputs agree. The packaged checks are replayed after extracting the source archive; the PDF is compiled and visually inspected before release.

## Limits

These are exact finite checks and a written self-audit, not formal certification or independent human review. The universal statement rests on the mathematical proof and the cited inputs. Bounded primary-source searches did not identify this connected single-triangle construction; they do not certify priority. The separate all-triangle-free-root question, the minimum possible order and a general classification remain unaddressed. AI assistance is disclosed in the manuscript prose.