Let G be a $(\frac{n}{2} + 1)$-regular bipartite graph with n vertices in each part. How to prove that this graph contains hamiltonian cycle?
I have already tried to use Ore's theorem or modify it to apply to bipartite graphs, but it didn't help. Also I've checked some papers (didn't find anything suitable in this situation).
Maybe you can give me some ideas how to solve this problem
It’s possible to modify a proof of Ore’s theorem.
Let $V$ and $W$ be the parts of $G$. If $G$ has no Hamilton cycle, keep adding edges between $V$ and $W$ that do not create a Hamilton cycle until you cannot add any more without creating a Hamilton cycle; call the resulting bipartite graph $H$. There must be a $v\in V$ and a $w\in W$ that are not adjacent in $H$, so adding the edge $\{v,w\}$ would create a Hamilton cycle; let $P$ be the Hamilton path
$$v=u_1,u_2,\ldots,u_{2n}=w\,.$$
For $k=1,\ldots,n$ consider the vertices $u_{2k-1}\in V$ and $u_{2k}\in W$. If $H$ contained both of the edges $\{u_1,u_{2k}\}$ and $\{u_{2k-1},u_{2n}\}$, $H$ would contain the Hamilton cycle
$$u_1,u_2,\ldots,u_{2k-1},u_{2n},u_{2n-1},\ldots,u_{2k},u_1\,,$$
so at most one ot the edges $\{u_1,u_{2k}\}$ and $\{u_{2k-1},u_{2n}\}$ can be in $H$. But then
$$2\left(\frac{n}2+1\right)=n+2\le\deg v+\deg w\le n\,,$$
which is absurd, so $G$ must have a Hamilton cycle.