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?
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?
Copyright © 2021 JogjaFile Inc.
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
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.