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.