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