The representation number 
of a word-representable
graph 
is the least positive integer 
for which 
has a 
-uniform representing word. The vertices of 
form the alphabet, every graph
vertex occurs exactly 
times, and two distinct vertices
are adjacent precisely when their occurrences alternate in the word.
Akgün et al. (2019) enumerated connected graphs by representation number. For 
, 2, ..., the numbers having representation number 2 begin
0, 0, 1, 5, 20, 109, 788, 8335, 117282, ... (OEIS A319489),
while the numbers having representation number 3 begin 0, 0, 0, 0, 0, 1, 39, 1852,
88838, ... (OEIS A319490).
Writing 
for the total number of vertices, Colbrook and Drysdale
(2026) proved that every bipartite graph 
with 
satisfies
![R(G)<=[N/4],](/images/equations/RepresentationNumber/NumberedEquation1.svg) |
(1)
|
where ![[x]](/images/equations/RepresentationNumber/Inline12.svg)
is the ceiling function. Among all bipartite
graphs on 
vertices, the maximum is attained by the 
-crown graph 
, with
![R(K_(n,n)-M)={2 for 1<=n<=3; 3 for n=4; [n/2] for n>=5.](/images/equations/RepresentationNumber/NumberedEquation2.svg) |
(2)
|
The finite cases were certified by checked Boolean unsatisfiability certificates, and the theorem was also formalized in Lean.
Colbrook and Drysdale (2026) report that discussions with ChatGPT 5.5, 5.6, and 6 contributed to the ordering method, obstruction classification, and odd-part argument. They also used Codex for combinatorial counting, certificate construction and verification, and Lean formalization, and state that they reviewed and adopted all content.
