An extension of Dirac Theorem

100 Views Asked by At

Following a related proof of Dirac theorem, I want to show that if $G$ is a balanced bipartite graph of order $n$ with minimum degree more than $n/4$, then $G$ has a Hamilton cycle.

Dirac's theorem: an $n$-vertex graph in which each vertex has minimum degree at least $n/2$ must have a Hamiltonian cycle.

$\textit{(Not sure about what I've done)}$: Let the given minimum degree be $N=\delta(G) > n/4,$ then by extension of Dirac's theorem: an $N$-vertex graph in which each vertex has a minimum degree at least $N/2$ must have a Hamiltonian cycle.

We then apply Ore's theorem: if $\deg(v_1) + \deg (v_2) \ge N$ then G is Hamiltonian.

Suppose there is any two non-adjacent vertices $v_1\in X$ and $v_2 \in Y$. Then $\deg(v_1) > N$ and $\deg(v_2) >N.$ So by Ore's theorem, we have $\deg(v_1) + \deg (v_2) > N + N = 2N > N$ or $2 \left(\frac{n}{4}\right) > \left(\frac{n}{4}\right) = \left(\frac{n}{2}\right)> \left(\frac{n}{4}\right)$

$\Rightarrow G$ is Hamiltonian by Ore's theorem.

$\Rightarrow G$ has Hamiltonian cycle by Dirac's theorem.

$\textbf{Note:}$ If $v_1\in X$ and $v_2 \in Y$ are any two adjacent vertices then $\deg(v_1) > N+1$ which contradicts $N=\delta(G) > n/4.$