Near-Perfect Matching
Probability
Level
1
Which of the following graphs exhibits a near-perfect matching ? The matching is indicated by red.
c
b
None of the above
a
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.
1 solution
The answer is c.
In c, there is only one vertex not connected to any edge in the matching — this is the definition of near-perfect matching. Graph b is perfectly matched since all nodes are connected to an edge in the matching. Graph a has several nodes not connected to edges in the matching and is neither perfect nor near-perfect.