Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

iff

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|improve this question
4  
It's not true that everyone knows the theorem. I do not! ;) –  Arkamis Oct 29 '12 at 18:57
add comment

2 Answers

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|improve this answer
add comment

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|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
add comment

Your Answer

 
discard

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.