No 8-regular graphs with distinct triangle counts among vertices exist
There is no $8$-regular $K_3$-irregular graph
Discrete Mathematics
Summary
Some graphs have a special property where each point (vertex) belongs to a unique number of triangles, called being triangle-irregular. The authors proved that if every point connects to exactly 8 others, such a graph cannot exist. Previous work found such graphs for 9 or more connections but none for 7 or fewer. By ruling out all possible sizes for the 8-connection case, they showed these special graphs only appear when points have at least 9 connections.
What this means in practice
- •For network designers: Avoid configurations where every node has a unique triangle count if all nodes have exactly 8 connections, helping simplify network topology design constraints.
- •For graph algorithm developers: Use the proof that 8-regular K3-irregular graphs do not exist to optimize algorithms that analyze triangle-based properties in graphs with uniform degree 8.
A theory result. No direct application yet.
Authors
Artem Hak, Sergiy Kozerenko, Andrii Serdiuk
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'c 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\geq 9$.