Determine all integers r≥ 0 for which there exists a finite simple r-regular graph G such that the triangle-degrees are pairwise distinct: for every vertex v∈ V(G), let operatornametd_G(v)=|x,y⊆ V(G):v,x,y spans a triangle in G|; require that operatornametd_G(u)≠operatornametd_G(v) for all distinct u,v∈ V(G). Recent preprints claim that such a graph exists if and only if r≥ 9.

Regular K3-irregular graph existence problem

The problem asks when a regular graph can give every vertex a different number of triangles. Recent preprints claim the exact answer is that such graphs exist precisely in regularities $r \ge 9$ .

Known results

Hak, Kozerenko, and Serdiuk (2025): no examples for $r \le 7$ , six possible orders for $r=8$ , and an explicit example for $r=9$ .
Hak, Kozerenko, and Serdiuk (2025): computational examples for every $r \in \{9,\ldots,30\}$ , but no proof for all larger $r$ .
Stevanović et al. (2024): examples for $r \in \{10,11,12\}$ .

September 2026 claimed resolution

Zhanhe Zhang’s preprint, posted September 11, 2026, claims constructions for every $r \ge 9$ , using threshold blocks, prescribed-margin switches, symbolic arguments, and finite verification. A later preprint by Hak, Kozerenko, and Serdiuk claims to eliminate all six possible orders for $r=8$ , yielding the complete criterion $r \ge 9$ ; both claims remain unverified.

Current status (as of October 2026): The known nonexistence results for $r \le 7$ and the claimed exclusion of $r=8$ are supplemented by claimed constructions for every $r \ge 9$ , but the complete resolution remains unverified.

Regular K3-irregular graph existence problem

Primary source

Additional references

Progress summary

Solutions 0