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$.
Best Answer
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.
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} . $$
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.