Are G and H necessarily isomorphic?

359 Views Asked by At

Let $G$ and $H$ be two simple graphs, both of them with seven vertices, each of which is of degree 2. Are G and H necessarily isomorphic?

The graphs $G$ and $H$ must have a cycle since each vertex is of degree 2 and therefore they are isomorphic.In general, this should be true for a graph with $n$ vertices with the above property? Is this correct?

1

There are 1 best solutions below

2
On BEST ANSWER

No; one of them could be $C_7$ (the $7$-vertex cycle) and the other could be the disjoint union of $C_3$ and $C_4$.

If you additionally knew that the graphs were connected, then there would be only one possibility.