Unique Trianlge Count sequence

Question

Consider a simple graph $G(V,E)$, such that $V = \{1,2,\dots, n\}$. We can define the triangle count of a vertex as follows:

$\Delta(v) = $ Number of triangles in the graph such that $v$ is one of the three endpoints of the triangle

By definition, $0 \leq \Delta(v) \leq {n-1 \choose 2}$.

Is there a graph $G$ such that each vertex in the graph has a unique triangle count? I have been able to answer this question, and the answer is yes. However, I will not give the answer, since I want you to try it yourself and come up with different graphs.

My questions are as follows:

1. Which is the smallest graph (in terms of the number of vertices) which has a unique triangle count sequence property? (please exclude the one vertex graph)
2. For what number of nodes ($n$) does there not exist a graph with the unique triangle count sequence property?

Answer 1

1. The smallest graph with the unique triangle count sequence property has 7 vertices.

2. The values of n for which there does not exist a graph with the unique triangle count sequence property are 2, 3, 4, 5, and 6.

It will be proven that for $2\le n\le 4$ it is impossible to form a graph with the unique triangle count sequence property.

1. $n=2\Rightarrow$ Both vertices will have TC 0 (a triangle cannot be constructed with only 2 vertices), and therefore the TCs are not unique.
2. $n=3\Rightarrow$ There are 2 cases:
   1. The edges do not form a triangle $\rightarrow$ every vertex has TC $0$
   2. The edges form a triangle $\rightarrow$ every vertex has TC $1$.
      In both cases, the TCs of the vertices are not unique.
3. $n=4$
   Consider that the maximum TC of each vertex is ${4-1\choose2}={3\choose2}=3$. Because there are 4 vertices, the TCs must be $0$, $1$, $2$, and $3$. But if one of the vertices has TC $0$, a triangle with it as a vertex would not be able to be formed, so the other 3 vertices would have to independently form a graph with the unique triangle count sequence property.
   It has been proven before that a 3-vertex graph with the unique triangle count sequence property cannot be formed.

The rest is shown in this picture:

For $n\ge9$ it will probably increase too. (I haven't checked - run time was ~5 mins for $n=8$ so it will be hours for $n=9$. Maybe a faster algorithm will work.)