The proof is basically the same as Lovász' proof that : It is well-known that the fractional chromatic number of a bridgeless cubic graph is 3. Therefore there is a probability distribution on the perfect matchings of such that given a random matching from this distribution, an edge is hit with probability 1/3.
Now let be and take perfect matchings from this distribution, and consider the probability that an edge is in none of them. This is , so by the union bound, the probability that every edge is in one of the matchings is greater than . Therefore there is some choice of perfect matchings that cover the graph.
log(n) bound
The proof is basically the same as Lovász' proof that
: It is well-known that the fractional chromatic number of a bridgeless cubic graph is 3. Therefore there is a probability distribution on the perfect matchings of
such that given a random matching from this distribution, an edge
is hit with probability 1/3.
Now let
be
and take
perfect matchings from this distribution, and consider the probability that an edge
is in none of them. This is
, so by the union bound, the probability that every edge is in one of the matchings is greater than
. Therefore there is some choice of
perfect matchings that cover the graph.