There is a cycle in G that contains all vertices of $P$ except (at most) one

Question

Let G be an $n$-by-$n$ bipartite graph with minimum degree $\delta> n/2$, and let $P$ be a maximal path in it. Prove that there is a cycle in G that contains all vertices of $P$ except (at most) one.

Actually it should be true without that maximality restriction, i.e. for an arbitrary path

How to approach this problem, with induction, contradiction ?

Answer 1

Let $P=v_1v_2\ldots v_m$.

If $v_1$ and $v_m$ are of the same colour, they have a common neighbour $w$ (because together they have $\ge 2\delta>n$ neighbours). Then $v_1v_2\ldots v_mwv_1$ is our desired cycle.

If $v_1$ and $v_m$ are of different colour, use $v_1$ and $v_{m-1}$ instead.

Answer 2

Although I do not think this is what you intended with this problem, technically this provides a solution to the problem as stated.

We have that $\delta(G) > \frac{n}{2}$, and so by a theorem of Moon and Moser ('63), we have that $G$ has a Hamiltonian cycle $C$. Since $C$ is a cycle that contains all the vertices of any path $P$, we are done.