Number of edges required to have a perfect matching 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.
 A: 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
A: I think that the optimal graph (maximum number of edges but no matching exists) will have one or two vertices disconnected from the rest.
A: Claim: The maximum size (number of edges) for connected graph $|G|=2k$ and $\Delta(G)=d$ to have no perfect matching is at least $dk-d$. For large $k$ the maximum size is $dk$, which is optimal.  
Let $G$ be a connected graph of order $|G|=n=2k$.
Let the maximum degree be $\Delta(G)=d$.
If $d=1$, then the graph is disconnected.
If $d=2$, then it is either disconnected or an even cycle, which has a perfect matching.
(Minimum size to be connected is $2k-1$)
In addition, there is a theorem that if $d(u)+d(v)\geq 2k$ for every non-adjacent $u,v\in V(G)$, then $G$ is Hamiltonian, which surely has a perfect matching.
(A converse of Dirac's theorem.)
Hence we need to further restrict $d< k$.
Hence we assume $3\leq d<k$.  
Let $m$ be the maximum size such that there is no perfect matching.
As Ben Derrett has pointed out, $m\leq dn/2=d(2k)/2=dk$.  
Since $G$ has no perfect matching, by Tutt's theorem $|X|<o(G-X)$ for some $X\subseteq G$.
For all such possible $X$, consider the case with largest $|X|$.
Suppose $|X|=k-1$. (It cannot be $>k-1$, else there are not enough odd components.)
For convenience, we let $G-X=W$.
Then $W=\lbrace u_1,\dots,u_{k+1}\rbrace$ and $X=\lbrace v_1,\dots,v_{k-1}\rbrace$.  
Since maximum degree is $d$, there are at most $d(k-1)=dk-d$ edges from $X$.
This happens when all edges are from $X$ to $W$.
Given that $d=3$, we may construct the $dk-d$ edges such that $G$ is connected.
Start with a path $P=u_1,v_1,u_2,v_2,\dots,u_{k-1},v_{k-1},u_k$, then add edge $v_{k-1}u_{k+1}$.
This ensures connectedness.
The remaining edges from $X$ to $W$ may be set arbitrarily.
We know the requirement of max degree $d$ can be met as $|W|>|X|$.  
However, after setting $dk-k$ edges, we cannot add any more.
Suppose instead that we add one more edge.
If cannot be from $X$ since all vertices are saturated.
Hence the edge is from $W$ to $W$.
But we may then check that $|X|<o(G-X)$ cannot be fulfilled.
Hence for the case where $|X|=k-1$, the maximum number of edges is $dk-d$.
Note: if we were to add more edges, then $|X|=r<k-1$.    
Edit: The case where $|X|=r<k-1$ seems to be the complicated part.
This seems to depend on the relative values of $d$ and $k$.
For example, I can find a graph of $|G|=16,m=24$ and $\Delta(G)=3$ with no perfect matching.
It should be possible to have $dk$ edges if $k$ is large enough.
(Something like $2k>3d$.)
Given that $d<k$, so that you have $2d<2k$ to work with, this is pretty close.  
Extra: For the general case without restriction on $d$, the maximum size also depends on $k$.
It may be checked that $m=3,10,19$ for $2k=4,6,8$ to have no perfect matching.
After that, $m=(k-2)(k-3)/2 + 2$.
This is by having a $K_{k-2}$ complete graph and last 2 vertices connected to $w\in K_{k-2}$.
