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
    $\begingroup$ Your thoughts? Matching of sizes 1 and 2 are easy to deal with, right? $\endgroup$ – asdf Sep 13 '18 at 10:12
  • $\begingroup$ Yes, for 2 I think we can only have a star, falls more or less by considering cases. But for 3 it becomes worse. $\endgroup$ – DesmondMiles Sep 13 '18 at 11:08
  • $\begingroup$ Then what happens if you consider an edge and remove its endpoints from the graph? $\endgroup$ – asdf Sep 13 '18 at 11:27
  • 1
    $\begingroup$ 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 $\endgroup$ – W.R.P.S Sep 13 '18 at 12:06

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$

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.

  • 1
    $\begingroup$ 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? $\endgroup$ – bof Sep 13 '18 at 12:00
  • $\begingroup$ @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. $\endgroup$ – ab123 Sep 13 '18 at 16:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.