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.

  • $\begingroup$ I think your intuition about modifying Dirac is probably the right one. $\endgroup$ – Austin Mohr Apr 29 '16 at 14:38
  • $\begingroup$ @AustinMohr I agree with you but how ??? that's the problem sir :) $\endgroup$ – Arman Malekzadeh Apr 29 '16 at 14:38

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.


Your Answer

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

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