= Solution
Take the <complete bipartite graph> $\boxed{K_{3,4}}$. Its seven <vertices> have degrees four on one side and three on the other. Deleting any two vertices leaves at least one vertex on each side, so the remaining complete bipartite graph is connected.
Every <cycle> in a <bipartite graph> alternates between its two parts, using equal numbers of vertices from each. A <Hamilton cycle> here would have to use three vertices from one part and four from the other, which is impossible. Thus \b[three-vertex connectivity and minimum degree three do not suffice] for Hamiltonicity in this seven-vertex example.
Back to article page
