I'm interested in determining how many edges are required in a graph in order to be certain that a perfect matching exists. I'm thinking of a general graph, not a bipartite graph. The conditions are that the number of vertices is even, and that the degree of any vertex can't be higher than a particular, pre-selected value. For example, how many edges are required in a graph consisting of 10 vertices, with no vertex higher than degree 4, to be certain that a perfect matching exists?
I hope this is a proper way to respond to answers on this site (first time here). Thanks for the feedback. I should have included that the graph is assumed to be connected. Also, yes, I want to know how many edges are sufficient, for a particular number of vertices and maximum vertex degree, for a perfect matching to exist.