Graph Theory – Prove Bipartite Graph with Odd Number of Vertices is Non-Hamiltonian

graph theoryproof-verification

Continuing with my studies in Introduction to Graph Theory 5th Edition by Robin J Wilson, one of the exercises asked to prove that, if $G$ is a bipartite graph with an odd number of vertices, then $G$ is non-Hamiltonian. This is what I've come up with. Is it strong enough?

Let graph $G$ be a bipartite graph with an odd number of vertices and G be Hamiltonian, meaning that there is a directed cycle that includes every vertex of $G$ (Wilson 48). As such, there exists a cycle in G would of odd length. However, by Theorem 2.1, a graph $G$ is bipartite if and only if every cycle of $G$ has even length (Wilson 33). Proven by contradiction, if $G$ is a bipartite graph with an odd number of vertices, then $G$ is non-Hamiltonian.

As an example, the picture below has 13 vertices so it must be non-Hamiltonian.

Best Answer

Yes, your proof is quite correct.

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 with cycles of odd number

Hints:

1) Clearly $u, w$ are connected in the cycle. It's a cycle, after all. Let's say they aren't connected by a length-2 path in $C$. Then the shortest path between them in $C$ is either of length $1$ or of length more than $2$. Show that either of these cases leads to some contradiction.

2) Take an $x\notin V(C)$ with $3$ distinct neighbours $u, v, w\in V(C)$. Use the result of 1) to discuss what $C$ must look like and again reach a contradiction.

Best Answer

Related Solutions

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

Graph with cycles of odd number

Related Question