[Math] Proof of Hamiltonian Cycle in a Complete Bipartite Graph

graph theoryhamiltonian-path

A complete Bipartite graph $K_{m,n}$ has a Hamiltonian cycle if and only if $m=n$.

I want to know if the following proof technique is correct. My proof will consider using proof by contradiction.

Assume that $m\not = n$. Let $H$ be the (Hamilton) cycle that goes through every vertex in $K_{m,n}$. $ H = v_0e_0v_1e_1…v_ie_i$. Since $K$ is bipartite, the cycle must alternate between the vertices on each side. Since $m\not = n$ there exists a $v_a = v_b, a < b$ inside cycle H. This leads to a contradiction since a cycle cannot have repeating vertices. Hence, a complete Bipartite graph $K_{m,n}$ has a Hamilton cycle if and only if $m= n$.

Is this correct?

Best Answer

Other direction can be prove in following way. As noted any cycle in bipartite graph will be of even length, and will alternate between the vertices of partite-sets. That means any Hamiltonian cycle in $K_{n,n}$ will have equal number of elements from both the partite-sets and as it covers entire vertex set, together we get $m=n$.

Related Solutions

[Math] Can a bipartite graph have many Hamiltonian paths but no Hamiltonian cycle

Yes! The Georges graph has this property. This graph is the smallest known counterexample to the Tutte conjecture that any 3-connected bipartite 3-regular graph is Hamiltonian. It has 50 vertices and 75 edges.

I verified that every vertex is the initial vertex of a Hamiltonian path with some Sage code:

def homtrac_orbits(g):
    orbits = g.automorphism_group(return_group=False, orbits=True)
    return all(g.hamiltonian_path(o[0]) is not None for o in orbits)

def report(G):
    print G.name() + ':', homtrac_orbits(G), G.is_hamiltonian(), G.is_bipartite()

report(Graph(">>graph6<<qO`a`_WO?O?_?_?OO???K?@O?B_?@??__?_I?A?_?_????@?A?@???\
O????g???`????C????????A?????O????C??????????K?????K?????S?????K?????\
B????OO?????__??????C??????C??????A?????C????????D_??????I???????[\
??????AG??????GA_", name="Georges"))

You can see it on SageCell but it takes some time to run. It prints "Georges: True False True" when complete.

The Ellingham-Horton graphs on 54 and 78 vertices are also homogeneously traceable but non-Hamiltonian. The 54-graph can be checked with

report(graphs.EllinghamHorton54Graph())

(included in the above SageCell). I also checked the 78-graph but this is too slow to include in the SageCell.

It seems reasonable to guess that the other known counterexamples to Tutte's conjecture—namely the Owens graph, the Horton 92-graph, and the Horton graph—are also homogeneously traceable, but checking in Sage is too slow for those to verify that way.

Graph Theory – Hamiltonian Bipartite Graph with ?(G) > k/2

As in Dirac, build to a maximal counterexample. That is, let $G$ be a bipartite graph with $\delta(G) > \frac{k}{2}$ and no Hamiltonian cycle. If any edge can be added to the graph that preserves all these properties, then do so.

Since $G$ is now a maximal counterexample, it has a Hamiltonian path $x_0 \cdots x_n$ (without loss of generality, $x_0 \in X$). Applying the pigeonhole principle to the high minimum degree (I leave the details to you), there are vertices $u \in X$ and $v \in Y$ such that

$x_0 \sim v$,
$x_n \sim u$, and
$u \sim v$.

The cycle $u v x_0 \cdots x_n u$ is Hamiltonian, which is a contradiction.

Best Answer

Related Solutions

[Math] Can a bipartite graph have many Hamiltonian paths but no Hamiltonian cycle

Graph Theory – Hamiltonian Bipartite Graph with ?(G) > k/2

Related Question