Maximum number of vertices of minimum degree in a graph consisting of only $3$-cycles

Question

Take a graph $G=(V,E)$ that consists of $n$ points. $3$-cycles make up all the edges in the graph. Moreover, there are exactly $n-2$ total $3$-cycles in the graph, and the minimum degree of the graph is $2$. Every vertex is contained on at least one $3$-cycle. Now, what is the maximum number of vertices of degree $2$? Moreover, the graph $G$ must be connected.

I understand that if we take $n$ vertices, we can draw exactly $\lfloor n/3\rfloor$ $3$-cycles so that all vertices still have degree $2$. Now, since we want to achieve exactly $n-2$ $3$-cycles, we obviously must add more of them, in which case we must start using vertices that already have degree $2$ to create these cycles. We then want to leave as many degree $2$ vertices "untouched" as possible. Having done this for smaller values of $n$, I am seeing that for $n=5$ the answer seems to be $2$, for $n=6$ and $n=7$ it seems to also be $2$, but for $n=8$ it looks like this is $3$ and so on. However, I am struggling to understand how exactly the structure works for large $n$, and if there would exist a formula for this (or perhaps a bound).

Answer 1

For $n>3$, you can attain $(n-2)$ degree $2$ vertices with the following graph. Letting the vertex set be $\{u,w,v_1,v_2,\ldots,v_{n-2}\}$, the edges are $\{uw\} \cup \{uv_i : i \in [n-2]\} \cup \{wv_i : i \in [n-2]\}$.

This is optimal:

1. If instead every vertex has degree $2$, the graph must be a disjoint union of cycles. Connectedness implies that it is a single cycle, but combined with the fact that all vertices are in a $3$-cycle, we arrive at a contradiction.
2. Suppose every vertex but one has degree $2$. Call this vertex $v$ and let its neighbours be $v_1,v_2,v_3,\ldots,v_k$. Because any $v_i$ is in a triangle, the other neighbour of $v_i$ (other than $v$) must be some $v_j$. In light of this, to ensure connectedness, the set of $\{v_i\}$ is forced to be $V \setminus \{v\}$. However, this construction yields $\le \frac{n-1}{2}$ triangles, which is less than required, completing the proof.