Maximum number of leaf blocks in 3-regular (cubic) graph

Question

The definition of block is

Block of $G$ is a maximal subgraph $G'$ of $G$ with no cut vertex of $G'$ itself.

Of course, there can exist many blocks in $G$.
In particular, isolated vertices, edges in bridge, and maximal $2$-connected subgraph of $G$ are blocks of $G$.

The definition of leaf block is

Leaf block of $G$ is a block of $G$ containing only one cut-vertex of $G$.

First, I found a lemma about $k$-regular tree, whose vertices except leaves have degree $k$.

Lemma: If a tree $T$ of order $n$ has $m$ vertices of degree $k$ and $n-m$ leaves, $k−1$ must divide $n−2$.

Proof: By handshaking lemma, $$ km + (n-m) = \sum_{v \in V(T)} \deg(v) = 2\vert E(T) \vert = 2(n-1)$$ Then $$ (k-1)m=n-2 $$ Since all terms $\in \mathbb{Z}$, $k-1$ divides $n-2$.

I will use $(k-1)m=n-2$ part here.
And this is my guess:

To make the cubic graph with maximum # of leaf blocks, make a $3$-regular tree, and change its leaves into the smallest $3$-regular leaf blocks.

I think the smallest $3$-regular leaf block is as following (but not certain):

So my conclusion is

Suppose $G$ of order $n$ has $\ell$ number of leaf blocks. First, we construct a $3$-regular tree with $n-4\ell$ vertices and $\ell$ leaves. By the lemma, $2(n-5\ell)=n-4\ell-2$. Then $\ell=\frac{n+2}{6}$. After constructing a tree with $n-4\ell$ vertices, change all leaves into the smallest $3$-regular leaf blocks shown above. It adds $4$ vertices to each leaf. Then we can make a $3$-regular graph with $n$ vertices and $\ell$ leaf blocks.

But there are so many assumptions, and such tree exists only when $n \equiv 4$ (mod 6).
So I cannot conclude $\ell = \lfloor \frac{n+2}{6} \rfloor$ is the maximum. Would you help me?

Answer 1

Yes, your conjecture is true. In fact, we can prove something stronger. All the extremal examples actually come from your construction. Say that a graph is special if it can be obtained from a $3$-regular tree $T$ (a tree where every vertex has degree $1$ or $3$) by replacing each leaf with the gadget in your picture.

Lemma. Let $\ell \geq 2$, and let $G$ be a smallest connected cubic graph with exactly $\ell$ leaf blocks. Then $G$ is special.

Proof. Let $B_1, \dots, B_\ell$ be the leaf blocks of $G$ and $x_1, \dots, x_\ell$ be the cut-vertices of $G$ such that $x_i \in V(B_i)$. Fix $i \in [\ell]$. Since $B_i$ is $2$-connected, $\deg_{B_i}(x)=2$. Therefore, $B_i$ has $|V(B_i)|-1$ vertices of degree $3$ and exactly one vertex of degree $2$. The smallest such graph with this property is the gadget, and it is the unique smallest graph. Therefore, by the minimality of $|V(G)|$, each $B_i$ is isomorphic to the gadget. Since $G$ is cubic, $x_1, \dots, x_\ell$ are distinct vertices. Let $Y= \bigcup_{i \in [\ell]} V(B_i) \setminus \{x_i\}$ and $T=G-Y$. Since $G$ is connected, $T$ is a connected graph with exactly $\ell$ vertices of degree $1$ and $|V(T)|-\ell$ vertices of degree $3$. The smallest such graph with this property is a $3$-regular tree. By the minimality of $|V(G)|$, it follows that $T$ is a $3$-regular tree. In other words, $G$ is special. $\square$

The smallest cubic graph with exactly one leaf block is $K_4$, which technically is not covered by the above lemma.

Corollary. Every connected $n$-vertex cubic graph has at most $\lfloor \frac{n+2}{6} \rfloor$ leaf blocks.

Proof. If $G$ is a connected $n$-vertex cubic graph with exactly $\ell$ leaf blocks, then $G$ has at least as many vertices as a special graph with $\ell$ leaf blocks by the previous lemma. Thus, $n \geq 6\ell-2$. $\square$