I have these three graphs (in the image below, sorry for poor quality it's on microsoft paint)

I need help proving that X is not isomorphic to Y and that X is not isomorphic to Z.

I have a very non-elegant solution IMO in which I examine each individual vertex's distance from the other 11, classifying them based on that, and showing that one class has four vertices which are connected in one but which are not connected in the other.

I would like to see a more elegant solution in which the isomorphism is proven through a written argument (no adjacency matrices, please)!

  • $\begingroup$ Every vertex in $Y$ is part of a $5$-cycle; this is true of no vertex in $X$. $\endgroup$ – rogerl May 9 '15 at 1:38
  • $\begingroup$ It might be easier to describe an answer to your question if the vertices in your figure were labeled. $\endgroup$ – bof May 9 '15 at 1:39
  • 1
    $\begingroup$ $X$ is $2$-colorable (bipartite), while $Y$ and $Z$ contain cycles of length $5$. $\endgroup$ – bof May 9 '15 at 1:45
  • $\begingroup$ For some reason, "$Y$ is not isomorphic to $Z$" was not part of the question. In fact, no two of the graphs are isomorphic: $X$ is the only bipartite graph among the three, and $Y$ is the only planar graph. (It's easy to see that $Y$ can be redrawn as a plane graph; $X$ and $Z$ both contain subdivisions of $K_{3,3}$.) $\endgroup$ – bof May 9 '15 at 1:52

No two of your three graphs are isomorphic.

$X$ is not isomorphic to $Y$ or $Z$, because $X$ is $2$-colorable, while $Y$ and $Z$ contain $5$-cycles.

$Y$ is not isomorphic to $X$ or $Z$, because $Y$ is planar, while $X$ and $Z$ contain subgraphs isomorphic to subdivisions of $K_{3,3}.$


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.