Question

Consider the following statements:

$S_1:$
If G has a perfect matching then number of vertices in G is even

$S_2:$
If number of vertices in G is even then G has a perfect matching

Which of the following is true?

• A. $Neither{S}_{1}not{S}_{2}istrue$
• B. $S_{1}istrueand{S}_{2}isfalse$
• C. $S_{1}isfalseand{S}_{2}istrue$
• D. $Both{S}_{1}and{S}_{2}aretrue$

Answer 1

The correct option is B $S_{1}istrueand{S}_{2}isfalse$

option (a)

The necessary condition for the existence of perfect matching is number of vertices in the graph should be even.

$\therefore S_{1}istrue$

A graph with even number of vertices may not contain a perfect matching.

For example:


For the graph shown here, perfect matching does not exists even though the graph has even number of vertices.