Perfect Matching
Probability
Level
1
Which of the following graphs exhibits a perfect matching ? (the matching is indicated in red)
b
None of the above
a
c
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
The answer is b. The red parts of the graph indicate the matching.
All of the vertices in b are touching edges. In c, one vertex is not touching any edge in the matching, and in a, there are several vertices not touching any edge in the matching.