A bipartite graph like $G(X,Y)$ such that $|X|=|Y|=k$ and $\delta(G) \gt \frac {k}{2}$ is Hamiltonian.

Question

A bipartite graph (or bigraph) is a graph whose vertices can be divided into two disjoint sets $X$ and $Y$ (that is, $X$ and $Y$ are each independent sets) such that every edge connects a vertex in $X$ to one in $Y$.

A Hamiltonian cycle, also called a Hamiltonian circuit, Hamilton cycle, or Hamilton circuit, is a graph cycle (i.e., closed loop) through a graph that visits each node exactly once.

A Hamiltonian graph is a graph which contains a Hamiltonian cycle.

Now Prove that: A bipartite graph like $G(X,Y)$ such that $|X|=|Y|=k$ and $\delta(G) \gt \frac {k}{2}$ is Hamiltonian. Note: I tried to prove this question the same as proving Dirac's Theorem but it didn't work! I don't reach the contradiction. Also I tried to prove it using Ore's theorem but it doesn't fit the condition of using Ore's theorem.

Answer 1

As in Dirac, build to a maximal counterexample. That is, let $G$ be a bipartite graph with $\delta(G) > \frac{k}{2}$ and no Hamiltonian cycle. If any edge can be added to the graph that preserves all these properties, then do so.

Since $G$ is now a maximal counterexample, it has a Hamiltonian path $x_0 \cdots x_n$ (without loss of generality, $x_0 \in X$). Applying the pigeonhole principle to the high minimum degree (I leave the details to you), there are vertices $u \in X$ and $v \in Y$ such that

• $x_0 \sim v$,
• $x_n \sim u$, and
• $u \sim v$.

The cycle $u v x_0 \cdots x_n u$ is Hamiltonian, which is a contradiction.