2
$\begingroup$

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.

Improve this question
$\endgroup$
2
  • 2
    $\begingroup$ ... 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. $\endgroup$
    – D.W. ♦
    Commented Feb 21, 2014 at 0:41
  • 2
    $\begingroup$ 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). $\endgroup$
    – David Richerby
    Commented Feb 21, 2014 at 12:38

1 Answer 1

Reset to default
2
$\begingroup$

Are you by any chance looking for Hall's theorem ? It gives a complete characterization of when a bipartite graph admits a perfect matching. Specifically:

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$.

Improve this answer
$\endgroup$
1
  • $\begingroup$ That's very relevant, there's also Tutte's theorem which is a generalised version for general graphs (I followed the wiki link). These theorems give necessary and sufficient conditions for perfect matching, but they talk about properties of all subsets of vertices in the graph. I suppose my question can be seen as "Is there a number, such that if the degree of every vertex in the graph is equal to or greater than that number, then Hall's\Tutte's conditions are surely fulfilled" $\endgroup$
    – Ron Teller
    Commented Feb 19, 2014 at 9:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.