Create a graph G with the following properties: - G has 7 vertices - G is bipartite - It has 12 edges - It does not contain a Hamilton cycle
And create a graph H such that: - G has 7 vertices - H has 12 edges - H contains a Hamilton cycle
For G, my idea is that there should be two sets of vertices, A and B, with |A|=4, |B|=3, and somehow creating a graph satisfying these conditions above?
For H, I've got C7 (cycle with 7 vertices), so do I just add any 5 edges?
(1) For the first part you can put two rows of vertices; one row (call it A) with 4 vertices, the other (call it B) with 3 vertices. Then, draw all the edges that go from the vertices in row A to the vertices in row B. I think this is called the complete bipartite $3,4$ graph $K_{3,4}$.
The graph is not going to have a hamiltonian cycle because:
In the Hamiltonian cycle, in a bipartite graph, in between each vertex from the row A there must be a vertex from row B. This forces the same number of vertices in each row. But that is not the case $3\neq4$.
(2) For the second part put the 7 vertices in a circle. The circle will form the edges of the Hamiltonian cycle. The circle forms 7 edges. So, add another 5 edges anywhere.