Prove that for every 10 regular graph with n>=200 vertices there is a matching of size 53? Prove that for every 10 regular graph with n>=200 vertices there is a matching of size 53?
any tips or hints would be appreciated
 A: Let $G$ be a $10$-regular graph with at least $200$ nodes. Recall the definition of maximal matching. Let $M$ be any maximal matching in $G$, and let $V$ be the set of all nodes of $G$ that is present in $M$, and let $W$ be the set of all nodes of $G$ that is not present in $M$ (so that $V \cup W$ is the set of all nodes in $G$).
Since $M$ is a maximum matching, there cannot exist two nodes in $W$ that share an edge (since it would imply that $M$ is not maximal, since we can add these pair of nodes to $M$). Since $G$ is $10$-regular, there must exist at least $10|W|$ edges going out from nodes in $W$. These edges must all connect one node in $W$ to one node in $V$. Since $G$ is $10$-regular and $M$ is a matching, there can be at most $9|V|$ edges connecting a node in $V$ to a node in $W$. Thus we have $9|V| \ge 10|W| = 10(n-|V|)$. Since $n \ge 200$, we have $|V| \ge 106$ (since $|V|$ must be an integer. Recalling the definition of $V$, we reached the conclusion that $|M| \ge \frac{1}{2} 106 = 53$.
