# 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.
{"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 1, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 34, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0, "url": "https://math.stackexchange.com/questions/4632993/can-a-class-of-3-regular-graphs-with-n-vertices-having-the-matching-number", "fetch_time": 1718403689000000000, "content_mime_type": "text/html", "warc_filename": "crawl-data/CC-MAIN-2024-26/segments/1718198861575.66/warc/CC-MAIN-20240614204739-20240614234739-00054.warc.gz", "warc_record_offset": 343897362, "warc_record_length": 36724, "token_count": 928, "char_count": 2995, "score": 3.8125, "int_score": 4, "crawl": "CC-MAIN-2024-26", "snapshot_type": "latest", "language": "en", "language_score": 0.8900970816612244, "file_path": "/sailhome/yjruan/project/latent-lm/data/processed/finemath-4plus/finemath-4plus/train-00041-of-00064.parquet"}