# Can a class of $3$- regular graphs with $n$ vertices having the matching number $\frac{7}{16}n$ be constructed?

The matching number $$\alpha'(G)$$ of graph $$G$$, sometimes known as the edge independence number, is the size of a maximum independent edge set

This question was prompted by this post.

Misha Lavrov have proved that the matching number of every $$3$$-regular graph with $$n$$ vertices is at least $$\frac{7}{16}n$$.

So my question is, is it possible to construct a class of $$n$$-order $$3$$-regular graphs such that the matching number is exactly equal to $$\frac{7}{16}n$$.

Note that $$\frac{7}{16}n<\frac{n}{2}$$. So by Petersen theorem we know that $$G$$ has a cut edge. I have noticed that the graph below satisfies the condition, but is it possible to construct more? Can infinite number be constructed?

In the above 3-regular graph(with 16 vertices), $$\alpha'(G)=7=\frac{7}{16}\times 16$$.

• There is a trivial example of disjoint copies of your example. One thing to try might be to make a 32 node graph from two of this one, and then see if you can swap some edges to connect them while keeping $\alpha'$ constant Commented Feb 5, 2023 at 17:45
• @AlexK Yes, in the connected case your method might work. Commented Feb 6, 2023 at 2:49
• @AlexK We cannot keep α′ constant when the graph with $32$ vertices is connected. See my answer, Commented Feb 6, 2023 at 9:48

Firstly, many thanks to Alex K. I have consulted a literature and found that when a $$3$$-regular graph is connected, this bound can be improved to $$\frac{4n-1}{9}$$. And the bound is tight.

• [1] Biedl, T., Demaine, E.D., Duncan, C.A., Fleischer, R., Kobourov, S.G.: Tight bounds on maximal and maximum matchings. Discrete Math. 285, 7–15 (2004)

Theorem 13. [1] Any 3-regular connected graph of order $$n$$ has a matching of size $$\frac{4 n-1}{9}$$.

Note that $$\frac{4 n-1}{9}-\frac{7}{16}n=\frac{n}{144}-\frac{1}{9}$$. A $$36$$-order 3-regular connected graph has a maximum matching with size at least $$15$$.

Proof. Let $$G$$ be a 3-regular graph of order $$n$$. By Theorem 11 and Lemma $$12, G$$ has a matching of size $$\frac{3 n-2 \ell_2}{6} \geqslant \frac{3 n-\frac{n+2}{3}}{6}=\frac{8 n-2}{18}=\frac{4 n-1}{9} .$$

Theorem 11. Any 3-regular graph $$G$$ of order $$n$$ has a matching of size $$\frac{3 n-2 \ell_2}{6}$$, where $$\ell_2$$ is the number of leaves in the 2-block tree of $$G$$.

Lemma 12. The 2-block tree of any 3-regular graph of order $$n$$ has at most $$\frac{n+2}{6}$$ leaves.

The bound in Theorem 13 is tight, which can be seen by attaching the smallest possible 3-regular graph to every leaf of the graph as follows.

The resulting graph, shown in the following picture, is defined for $$n \equiv 16$$ mod 18. There are $$\frac{n-7}{9}$$ black vertices, inducing $$\frac{4 n-10}{18}$$ odd components. Hence, any matching has at least $$\frac{4 n-10}{18}-\frac{n-7}{9}=\frac{n+2}{9}$$ unmatched vertices and therefore at most $$\frac{8 n-2}{9}$$ matched vertices.