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.
Best Answer
The literature about matchings, in particular perfect mathchings is vast. There is a classic book of Lovasz and Plummer: http://books.google.com/books/about/Matching_theory.html?id=yW3WSVq8ygcC
and this paper may also be of interest:
http://journals.cambridge.org/article_S0013091500009809