Skip to main content
1 of 4
Fedor Petrov
  • 108.9k
  • 9
  • 264
  • 459

We may use Tutte maximal matching theorem (in Berge's form) instead of Edmonds matching polytope theorem, as in the proof by Sam Fiorini provided by Tony Huynh.

Denote by $n, m$ the number of vertices and arcs respectively. If the maximal matching covers all vertices but $t$, that is, it size equals $(n-t)/2$. Then, by Tutte--Berge there exists a set $S$ of vertices such that $G^\ast-S$ has at least $|S|+t$ components $C_1,\ldots,C_{k}$, $k\geqslant |S|+t$ (we may even achieve that the number of odd components is not less than $|S|+t$, but we do not care whether they are odd or no.) Each component $C_i$ contains a vertex $v_i$ from which there is no arc inside $C_i$ (otherwise we have a cycle). All arcs from $w_1,\ldots,w_k$ go to $S$, and since indegrees in $S$ do not exceed 2, we conclude that there exist at most $2|S|$ arcs going from $v_i$'s, and at most $2$ arcs from each of $n-k$ other vertices, in total at most $2(n-k+|S|)\le 2(n-t)$ arcs. Thus, $m/4\leqslant (n-t)/2$, as needed.

Fedor Petrov
  • 108.9k
  • 9
  • 264
  • 459