There is no $8$-regular $K_3$-irregular graph

Abstract

A graph is $K_3$-irregular if its vertices belong to pairwise distinct numbers of triangles. We prove that no $8$-regular $K_3$-irregular graph exists, settling the last unresolved case. Following the initial discovery of such graphs for regularities $r\in \{10,11,12\}$ (Stevanović et al., 2024), our previous work (Hak et al., 2025) showed that no such graphs exist for $r\le 7$, provided the first example for $r=9$, and proved that any $8$-regular candidate must have between $17$ and $22$ vertices. We exclude these possible orders for $r=8$ by combining careful analysis of triangle degrees with integer linear programming techniques. Meanwhile, a recent construction (Zhang, 2026) established that regular $K_3$-irregular graphs do exist for all $r\ge 9$. Together with our results, this establishes that an $r$-regular $K_3$-irregular graph exists if and only if $r\ge 9$.

arXiv commentUpdated version, properly adressed range {1..20} for n=20. Any comments are welcome