0
$\begingroup$

enter image description here

For example in the picture above.

I know that I need to calculate if both graphs have the same number of vertices and edges.

But I don't know what I should do next to check if the graphs are isomorphic or not.

$\endgroup$
1
  • 2
    $\begingroup$ The original title reminded me of this story. $\endgroup$
    – Asaf Karagila
    Jan 15 '16 at 15:08
5
$\begingroup$

Graph isomorphisms preserve the vertex degree, that is, the number of edges incident to a vertex. In $G'$, the vertex $w_5$ has degree $5$, but there is no vertex with degree $5$ in $G$. Thus, the graphs cannot be isomorphic.

$\endgroup$
1
  • 2
    $\begingroup$ There are many more obstacles to an isomorphism visible in these graphs: While both graphs have exactly one double edge and in both graphs the endpoints of this double edge have exactly one neighbour in common, this common neighbour is of degree 3 in the left graph and of degree 2 in the right graph ... $\endgroup$ Jan 15 '16 at 15:09

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.