Minimum perfect matching with uneven vertices? Given this graph, what is the minimum perfect matching? What do you do, when there is an uneven number of vertices?
A perfect matching is one that includes every vertex so only graphs with an even number of vertices can have a perfect matching. If the number of vertices is odd, there is simply no perfect matching.