2
$\begingroup$

I've narrowed the question down to three graphs, the first third and fourth graph, because the last graph has too many edges and the second graph is non-Hamiltonian while the other are. However, I'm not too sure how to find a relation between the rest of the graphs. Can anyone suggest a method of helping with isomorphism? I remember from lecture there was a way to take a sub graph and see if it's isomorphic however I don't entirely remember.

Thanks!

Here's the question.

$\endgroup$
  • 1
    $\begingroup$ The fifth graph has vertices of degree four. None of the other graphs do. $\endgroup$ – JMoravitz Jan 30 '17 at 6:06
0
$\begingroup$

The first and third are isomorphic. The easiest way, (when the graphs are as small as these), is to try and give the explicit isomorphism.

You should check for yourselve the other graphs too.

$\endgroup$
0
$\begingroup$

The first three graphs are all isomorphic. The fourth graph has cycles of length $5$, and the fifth graph has nodes of degree $4$ and cycles of length $3$.

An isomorphism of $(1,2,3,4,5,6,7,8)$ is $(9,15,11,13,16,10,14,12)$ for the second and $(24,19,20,23,17,18,21,22)$ for the third graph.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.