Petersen's theorem

Let Gi be a component with an odd number of vertices in the graph induced by the vertex set V − U.

By a simple double counting argument we have that where Ei is the set of edges of Gi with both vertices in Vi.

The theorem appears first in the 1891 article "Die Theorie der regulären graphs".

Schönberger strengthened Petersen's theorem in 1934 by showing that each edge of any cubic bridgeless graph belongs to some perfect matching.

The general case was settled by Esperet et al. (2011), where it was shown that every cubic, bridgeless graph contains at least

Based on Frink's proof[6] they obtain an O(n log4 n) algorithm for computing a perfect matching in a cubic, bridgeless graph with n vertices.

If G is a regular graph of degree d whose edge connectivity is at least d − 1, and G has an even number of vertices, then it has a perfect matching.