# Maximum number of edges in no 3-matching

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?

• Your thoughts? Matching of sizes 1 and 2 are easy to deal with, right? – asdf Sep 13 '18 at 10:12
• Yes, for 2 I think we can only have a star, falls more or less by considering cases. But for 3 it becomes worse. – DesmondMiles Sep 13 '18 at 11:08
• Then what happens if you consider an edge and remove its endpoints from the graph? – asdf Sep 13 '18 at 11:27
• Let $G=(V,E)$ be a graph with a vertex set $V = \{1,...,n\}$ and $4 \le 2s\le n$. If $G$ contains no matching of size $s$, then $|E|\le \text{max}\{\binom{2s-1}{2},\binom{n}{2}-\binom{n-s+1}{2}\}$ proof : Erdos conjecture on matchings in hypergraphs-Katarzyna Mieczkowska-Theorem 8 – W.R.P.S Sep 13 '18 at 12:06

## 1 Answer

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.

• I think we could all have figured out for ourselves the maximum number of edges in simple graph on $5$ vertices with no matching of size $3.$ How does that help to determine the maximum number of edges on $n$ vertices with no matching of size $3$ when $n\gt5?$ Is it supposed to be obvious? – bof Sep 13 '18 at 12:00
• @bof Yes, I realize it is non-trivial for $n \geq 6$. We can use Theorem 8 of the paper suggested by W.R.P.S in a comment to the question above. – ab123 Sep 13 '18 at 16:00