Let $G$ be a simple graph, with order $\nu$ even and minimum degree $\delta <\nu/2$. Show that if number of edges ($\epsilon$) in the graph be such that $\epsilon$ > $\delta \choose 2$ + $\nu - 2\delta-1 \choose 2$ + $\delta(\nu - \delta)$, then $G$ has a perfect matching.
I am supposed to use Tutte's Theorem here. By Tutte's Theorem, for any $S \subset V$, if the number of odd components in $G-S$ is less than or equal to the cardinality of $S$, then we have a perfect matching.
So, all I need to show is that for any $S\subset V$, $o(G-S) \leq |S|$. But I am having hard time establishing this from the inequality: $\epsilon$ > $\delta \choose 2$ + $\nu - 2\delta-1 \choose 2$ + $\delta(\nu - \delta)$.
I will greatly appreciate any help here. Thanks.
A few hints:
1) Minimum knowing the minimum degree is less than a certain value seems odd. Maybe we should be using this knowledge that there is a vertex of minimum degree $\delta$.
2) Given (1), have you considered the extremely simple choice for $S$?
3) That's a lot of edges. However, I believe the theorem can be strengthened. You actually only need $\epsilon > \binom{\delta}{2} + \binom{\nu - \delta - 1}{2} + \delta$.
4) I may just be cross, but consider using the normal Latin characters $n$ and $e$, as I don't think I've ever seen this Greek notation.
I should say, if you are still having difficulties, leave a comment explaining why. However, if you manage to find your own solution, post it as answer!