Find an example of a graph $G$ with 3 or more vertices that is regular, connected, bipartite, and contains no Hamilton cycle. Please give me a hint.
What I've got so far: Since $G$ is regular and bipartite, its two sets of vertices are of equal sizes. $G$ is probably $3$-regular because the more edges there are, the harder it is to avoid having a Hamilton cycle, but this isn't strictly necessary. I know I am supposed to construct $G $ so that the subgraph test for Hamilton cycle shows that $G$ doesn't have a Hamilton cycle.
Best Answer
I assume by the "subgraph test for Hamiltonian cycle" you mean the toughness test: if there is a way to delete $k>0$ vertices from the graph and leave more than $k$ connected components, then the graph is not Hamiltonian.
The smallest $k$ that works is $k=2$; $k=1$ runs into trouble with vertex degrees in the components. For example, there is a $3$-regular connected bipartite graph $G$ with two vertices $\{v,w\}$ such that $G - \{v,w\}$ has three components. This is necessarily not Hamiltonian.
(A good approach to see if there is a graph satisfying some conditions is to look it up on the House of Graphs. You can search for all graphs with the conditions
Bipartite = true AND Regular = true AND Connected = true AND Hamiltonian = false, and it will find you some examples.)