Graph with even vertices and ${n-1}\choose 2$ $+ 1$ edges has a perfect matching

combinatoricsdiscrete mathematicsgraph theoryhamiltonian-pathmatching-theory

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?

Best Answer

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.

Related Question