How many simple graphs (up to isomorphism) have 6 vertices and 8 edges and admit a Hamiltonian circuit

707 Views Asked by At

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?

2

There are 2 best solutions below

2
On BEST ANSWER

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$.

0
On

I believe these are the 6 graphs you need.

enter image description here