Prove or disprove: There exists an integer k such that every k-connected graph is hamiltonian.

I am quite sure that it is not true but am having difficulty showing this (Bow)

Printable View

- Sep 25th 2012, 02:01 AMdlucioHamiltonian Graphs
Prove or disprove: There exists an integer k such that every k-connected graph is hamiltonian.

I am quite sure that it is not true but am having difficulty showing this (Bow) - Sep 25th 2012, 04:17 AMjohnsomeoneRe: Hamiltonian Graphs
Consider complete bipartite graphs. When are they k-connected? When are they Hamiltonian?

ASIDE: These graphs are wonderful in graph theory. Other than complete graphs, my memory is that they show up more than any other class of graphs. They seem to often show up in theorems as "...is less than or equal to ... with equality holding only for complete bipartite graphs." They're complicated enough to be non-trivial, but simple enough to serve as concrete COMPUTABLE examples when examining a great many definitions and theorems. I'd advise keeping them as a "stock example" to make concrete the various definitions and theorems you encounter. - Sep 27th 2012, 11:12 AMdlucioRe: Hamiltonian Graphs
Yes works very well, I understand. Very useful construction. Thanks.