0
$\begingroup$

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...

  • 4
    It's not true that everyone knows the theorem. I do not! ;)2012-10-29

2 Answers 2

1

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.

  • 0
    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 $v$ertice 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.2012-11-05
1

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?