Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Everyone knows the Tutte's Theorem (necessary & sufficient condition for a graph to have a perfect matching - viz wikipedia page on Tutte's Theorem).

The deficient version of this Theorem is:

G has matching covering all vertices with exception of at most k vertices


for any subset S of V(G) holds that the number of odd components of G-S is at most |S|+k

Obviously, Tutte's Theorem is special case of deficient Tutte's Theorem for k equal to zero.

Can this version be somehow be easily proven with aid of the original Tutte's Theorem? E.g. with transformation of G to some more convenient graph, where Tutte's condition would hold...

share|cite|improve this question
It's not true that everyone knows the theorem. I do not! ;) – Emily Oct 29 '12 at 18:57

I think that the proof might work like this:

Let C be a complete graph of k vertices, we make a new graph C+G where we connect every vertice of C with every vertice of G.

Lets examine the Tutte condition in this graph.

  • If C is not a subset of S, the number of odd components is at most 1 because the part of C that is not in S connects all of the components in G together.

  • Otherwise the number of odd components can be at most |S intersection G|+k, but thats exactly how big S is.

Now that the Tutte condition works, we get a perfect matching. If you remove C from the matching the resulting matching will cover the vertices of G except at most k vertices.

share|cite|improve this answer
As pointed out there is a problem with the parity of G+C, if you add a correct complete graph, this method still works. But now im pretty sure there is a nicer way to do this. Adding a k-1 vertice complete graph for the case where the parity of k and |G| differs will fix this problem though. If k is odd and |G| even, you will never need more than k-1 unpaired vertices and same thing if k is even and |G| odd. – Tommassino Nov 5 '12 at 23:45

I don't think that this proof works, because Tutte condition doesn't have to be satisfied. What if graph C+G has an odd number of vertices?

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.