# Degree conditions sufficient for Hall's theorem

Let $G=(L,R,E)$ be a bipartite graph, are there conditions on the degree of the vertices under which the condition of Hall's theorem is surely satisfied? (meaning a perfect matching exists in the graph).

Konig's theorem proves that every $k$-regular bipratite graph has exactly $k$ edge disjoint perfect matchings, so the answer is obviously yes for any $k$-regular bipartite graph with $k>0$ (it's not hard to see why hall's condition is satisfied in this case).

Is there a wider rule?

For example: Let $|L|=|R|=n$, What is the minimal degree as a function of $n$ of every vertex in the graph such that the graph must admit a perfect matching?

I'm also wondering if these conditions will hold in general graphs (satisfying Tutte's theorem), and if not, then are there similar conditions for general graphs.

• ... Perhaps you are asking for a threshold $t$ (depending only upon $n$) such that, if every vertex has degree $\ge t$, then the graph will surely have a perfect matching. Is that it? If so, what have you tried? Have you tried constructing counterexamples? Have you tried building small graphs by hand that lack perfect matchings and where all vertices have large-ish degree? We expect you to make an effort on your own before posting here, and to show us what you've tried.
– D.W.
Feb 21 '14 at 0:41
• The Dirac, Ore and Bondy–Chvátal theorems give some degree conditions for Hamiltonicity. As you observed in an earlier version of the question, the existence of a Hamiltonian cycle implies a matching (at least, for graphs of even order). Feb 21 '14 at 12:38

G admits a perfect matching if and only if for all subsets $S \subset L$, we have $$|\Gamma(S)| \ge |S|$$ where $\Gamma(S) \subset R$ is the set of neighbors of vertices in $S$.