Which of the following graphs G V E has a perfect matching

Solution

(a) The graph odes not have a perfect matching. Becasue vertex 1 will not part of any edge as it not co-prime with anyother number. So a perfect matching does not exist for this graph

(b) There is an edge between two vertices if they have a common factor. There is a perfect matching for this graph, the perfect matching is:

4 6
8 10
12 14
16 18
20 24
26 28
30 32
34 36
38 40
42 44
46 48
50 52
54 56
58 60
62 64
66 68
70 72
74 76
78 80
82 84
86 88
90 92
94 96
98 100
9 15
21 27
33 39
45 51
57 63
69 75
81 87
93 99
25 35
55 65
85 95
49 91
22 77

(c) A perfect matching does not exist. As the multiplcation of two numbers is far two less, so there are many big numbers which need to connected with small numbers. There are two sets {1-48} {49,100} Now every number from second set should be mapped with one number from the first set. There are more numbers in second set than the first one. So one-one mapping is not possible.