Prove that a graph G without isolated vertices has a perfect

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

Solution

Proof:

By the Gallai theorem, we know that

If a graph G has no isolated vertex, then ’ (G) + ’(G) = v(G).

Let v(G)=n.

Since G has a perfect matching, so we know that n is even and ’(G)=n/2.

Then n/2+’(G)=n

Which implies that ’(G)=n-n/2=n/2

Thus, ’ (G) = ’(G).

Conversely, if G has no isolated vertices and ’ (G) = ’(G)

then we get ’ (G) + ’(G)=n

which implies that ’ (G) + ’(G)=n

2 ’(G)=n

’(G)=n/2, where n is even

Thus, G has a perfect matching.