# Prove that no bipartite graph of order $3$ or more is Hamiltonian connected

Prove that no bipartite graph of order $$3$$ or more is Hamiltonian connected

A graph $$G$$ is Hamiltonian connected if for every pair $$u,v$$ of vertices of $$G$$, there is a Hamiltonian $$u-v$$ path in $$G$$

Theorem 3.23: Let $$G$$ be a graph of order $$n$$ such that $$deg(v) \geq \frac{n+1}{2}$$ then $$G$$ is Hamiltonian connected.

this is what I got so far

Let $$G$$ be a bipartite graph with 2 partites $$U$$ and $$V$$. Assume that $$G$$ is connected, otherwise, we have nothing to prove. We will prove this by induction

Base: $$n=3$$, then either $$|U|=1$$ and $$|V|=2$$ or the other way around, there is a vertex of degree $$1$$, which is less than $$\frac{n+1}{2}$$, so $$K_{1,2}$$ isn’t Hamiltonian connected.

Inductive: Assume that for $$n=k$$, G isn’t Hamiltonian connected. That mean there is at least one vertex $$v$$ of degree less than $$\frac{k+1}{2}$$. Add a new vertex $$w$$ the connect $$w$$ to every vertex on the opposite partite

Case 1: $$w$$ is on the same partite of $$v$$ then $$deg(v)$$ is unchange, and $$G$$ still isn't Hamitonian connected.

Case 2: $$w$$ is on the opposite partite of $$v$$, Can this change my result?

It suffices to show that no complete bipartite graph is Hamiltonian connected, as any bipartite graph can be obtained from a complete one by removing edges. And removing edges cannot make a graph Hamiltonian connected.

So let $G$ be a complete bipartite graph with parts $X$ and $Y$.
If $|X| = |Y|$, take $u, v \in X$ (why must $u,v$ exist, by the way ?). No Hamiltonian path can start at $u$ and finish at $v$, since any Hamiltonian path starting in $X$ must finish in $Y$.

If $|X| < |Y|$, take $u \in Y, v \in X$. No Hamiltonian path can start at $u$ and finish at $v$, since any Hamiltonian path starting in $Y$ must finish in $Y$.

Similar when $|X| > |Y|$.

In fact I didn't even need to suppose $G$ was a complete bipartite graph...

I think the complete bipartite graph is Hamiltonian connected.

• complete bipartite with odd order isn't Hamiltonian connected, because if you start at a vertex in smaller partite, you will left out one vertex, but the bipartite with even order is Hamiltonian connected, at least that is what I see from the graph. Oct 30 '14 at 23:49