2
$\begingroup$

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?

$\endgroup$
1
0
$\begingroup$

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...

$\endgroup$
0
$\begingroup$

I think the complete bipartite graph is Hamiltonian connected.

$\endgroup$
1
  • 1
    $\begingroup$ 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. $\endgroup$ Oct 30 '14 at 23:49

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.