Graph with even vertices and ${n-1}\choose 2$ $+ 1$ edges has a perfect matching Let G be a simple graph with an even number n of vertices
   and suppose that G has at least $n-1\choose 2 $$+ 1$ edges.
   Prove that G has a perfect matching. 
I tried to use induction but I am confused, to finish. how can we use $2k\choose 2 $$+ 1$  vertices to deduce that graph has a perfect matching? or Is there any other way of proofing it? 
 A: Clearly, since it has $2k$ vertices, if we prove this graph is Hamiltonian then we are done.
If this graph satisfies Ore's condition, that is: for every non adjancent vertices the sum of their degrees is at least $n$; then we are done. 
Say exists nonadjancent vertices $A$ and $B$ such that $d_A=a$ and $d_B=b$ so that $a+b\leq n-1$. Say among all other $n-2$ vertices $m$ are connected to both of them (put all those vertices in the set $M$), so exactly $a-m$ vertices are connected just with $A$ (put them in the set $P$) and exactly $b-m$ vertices are connected to $B$ (put them in the set $Q$) and the rest of the vertices are not connected to $A$ and $B$. So 


*

*$m$ vertices can have at most degree $n-1$ and

*$(a-m)+(b-m)$ can have at most degree  $n-2$ and 

*all other $(n-2)-a-b+m$ can have at most degree $n-3$. 


So by the Handshake lemma we have $$2\varepsilon \leq (n-2-a-b+m)(n-3)+(a+b-2m)(n-2)+m(n-1)+(n-1)$$ 
So we have (and by the given condition we get) $$ 2\varepsilon\leq  n^2-3n+4\implies  \varepsilon=  {n^2-3n+4\over 2}$$
Which means that all vertices except $A$ and $B$ form a $n-2$ clique $K$. Now take vertex $A'$ in $P$ and vertex $B'$ in $Q$ and vertex $C$ in $M$. Clearly there is a path $\mathcal{P}$ in $K\setminus \{C\}$ that goes through all vertices in $K\setminus \{C\}$ that begins at $A'$ and ends at $B'$. So we have a cycle $$A'-...-B'-B-C-A-A'$$ and we are done.
