Petersen proved that every cubic graph without cut-edges has a perfect matching,
but some graphs with cut-edges have no perfect matching. The smallest cubic
graph with no perfect matching belongs to a general family applicable to many
problems on connected d-regular graphs with n vertices. These include the
smallest matching number for such graphs, and relationships between the
eigenvalues and the matching number and between eigenvalues and edge-connectivity in regular graphs.
This is partly joint work with Sebastian M. Cioaba and Doulgas B. West.