Maximum number of edges in no 3-matching

376 Views Asked by At

Let $G$ be a graph on $n$ vertices. Find the maximum possible number of edges if $G$ has no matching of size $3$.

Also, what happens with other sizes?

1

There are 1 best solutions below

2
On

Hint:
It is easy to see that the "best" case (i.e. to have maximum no. of edges) with a minimum amount of matchings possible is when the graph is completely connected. Now convince yourself that the completely connected graph $K_5$ with $n = 5$, i.e. with $10$ edges has no matching with $3$ edges

enter image description here $\quad$

Edit:
My answer is just a specific case ($n = 5$). For a general $n\geq 6$, you will have to use the result suggested by user W.R.P.S in the comment above for $s = 3$. It gives $\max\{10, 2n - 3\}$ as the answer to your question.