Isolated vertices perfect matching proof

1.1k Views Asked by At

Prove that a graph $G$ without isolated vertices has a perfect matching if and only if $\alpha'(G)=\beta'(G)$.

1

There are 1 best solutions below

0
On BEST ANSWER

-> If $G$ has no isolated points, then $\alpha'(G)+\beta'(G)=n$. Also, since $G$ has a perfect matching we know that $n$ is even and $\alpha'(G)={n\over 2}$. So ${n\over 2}+\beta'(G)=n$ implies that $\beta'(G)={n\over 2}$ and so $\alpha'(G)=\beta'(G)$.

<- If $G$ has no isolated points and $\alpha'(G)=\beta'(G)$, then since $\alpha'(G)+\beta'(G)=n$ implies that $2\alpha'(G)=n$ and so $\alpha'(G)= {n\over 2}$ where $n$ is even. Thus $G$ has a perfect matching.