How many simple graphs (up to isomorphism) have 6 vertices and 8 edges and admit a Hamiltonian circuit?
Apparently the answer is 6, but how would you prove this?
How many simple graphs (up to isomorphism) have 6 vertices and 8 edges and admit a Hamiltonian circuit?
Apparently the answer is 6, but how would you prove this?
Hint: Such a graph is $C_6$ with two extra edges. Enumerate the number of ways up to isomorphism to add two edges to $C_6$.