For which integers r≥ 0 does there exist a finite simple r-regular graph G such that, for every vertex v∈ V(G), the triangle-degree tau_G(v)=|x,y⊆ V(G):xy∈ E(G),,vx,vy∈ E(G)| is distinct from tau_G(w) for every other vertex w∈ V(G)? Equivalently, determine whether such a graph exists for each r; the claimed classification is that one exists if and only if r≥ 9.

Existence of regular K3-irregular graphs

The problem asks whether regular graphs whose vertices have pairwise distinct numbers of incident triangles exist at each regularity. Earlier work ruled out regularities $r \le 7$ , constructed examples for $r \ge 9$ in several cases, and left regularity $8$ open.

Known results

No examples exist for regularity $r \le 7$ .
An explicit $9$ -regular example has order $24$ .
Examples were reported for $r \in \{10,11,12\}$ and computationally through $r=30$ .
Any hypothetical $8$ -regular example would have order $17 \le n \le 22$ .

September 2026 claimed exclusion

Artem Hak, Sergiy Kozerenko, and Andrii Serdiuk claim that integer-linear programming and triangle-degree analysis eliminate every remaining order for regularity $8$ . If correct, this closes the classification; the claim is unrefereed and has not been independently corroborated in the retrieved sources.

Current status (as of September 2026): Regularities $r \le 7$ are excluded and examples are known for several $r \ge 9$ ; regularity $8$ is claimed impossible, but that claim remains unverified.

Existence of regular K3-irregular graphs

Primary source

Additional references

Progress summary

Solutions 0