1
$\begingroup$

How can I prove that no bipartite graph is hamiltonian-connected?

I thought I could use another problem of my homework: Ks,t is hamiltonian iff s=t But I don't really see how

Or Should I try induction?

$\endgroup$
1

1 Answer 1

Reset to default
1
$\begingroup$

You have all you need right now.

A graph is Hamilton-connected if any two vertices can be joined by a Hamilton path. So all you need to do is show that if two vertices from different parts of a bipartition can be joined by a Hamilton path, then two vertices from the same part cannot.

(With the exception of $K_{1,1}$, which is Hamilton-connected.)

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .