0
$\begingroup$

Let $G=(V,E)$ be a simple, undirected graph. A matching is a subset $M\subseteq E$ such that all members of $M$ are pairwise disjoint; moreover we call $M$ perfect if $\bigcup M = V$.

The 1-factorization conjecture states that if the minimum degree $\delta(G)$ is at least $n$ and $|V(G)| = 2n$, then $G$ has a perfect matching.

Dirac's theorem states that if $\delta(G)\geq n$ and $|V(G)| = 2n$, then $G$ has Hamiltonian cycle.

Given $G$ with $\delta(G)\geq n$ and $|V(G)| = 2n$, we can't we just take a Hamiltonian cycle and pick every second edge to get the desired perfect matching?

$\endgroup$
  • 1
    $\begingroup$ The 1-factorisation conjecture is that the edge set of $G$ has a decomposition into $1$-factors: so you have to repeatedly take out perfect matchings, but Dirac's theorem will only help you find the first two. $\endgroup$ – Ben Barber Apr 24 '17 at 9:39
  • 2
    $\begingroup$ Your are probably both aware of this, but: (0) the (necessary) condition that the graph be degree-regular has not been mentioned, (1) not only does a single Hamilton circuit only give two perfect matching, but after taking them out the minimum degree may drop, so you cannot keep going, (2) a proof of the conjecture for sufficiently large $n$ has been published by Csaba, Kuhn, Lo, Treglown: Proof of the 1-Factorization and Hamilton Decomposition Conjectures Memoirs of the American Mathematical Society, Volume 244, Number 1154, November 2016 $\endgroup$ – Peter Heinig Apr 25 '17 at 15:04
  • $\begingroup$ Corrected literature reference: Csaba, Kuhn, Lo, Osthus, Treglown: Proof of the 1-Factorization and Hamilton Decomposition Conjectures,Memoirs of the American Mathematical Society, Volume 244, Number 1154, November 2016 $\endgroup$ – Peter Heinig Apr 30 '17 at 19:07

Your Answer

By clicking "Post Your Answer", you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.