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