0
$\begingroup$

enter image description here

I know this graphs are not isomorphic. However they have the same number of vertex and edges, and the same degree sequence, is not the most easy case.

If im correct, the graphs are isomorphic if evey posible bijection between vertex preserve adjacencies, then if i find just one bijection in wich some adjacencies are not preserved, that will be enough to show they are not isomorphic?.

$\endgroup$
2
$\begingroup$

In the first graph, none of the vertices with degree $2$ are adjacent. In the second graph, there are two pairs of adjacent vertices with degree $2$.

$\endgroup$
2
$\begingroup$

It is the other way around: the graphs are isomorphic if there is some bijection in which the adjacencies are preserved. So if you were to do this by checking bijections, you'd need to check all of them(!).

In fact, graph isomorphism is generally a hard problem, but you can sometimes find characteristics of one graph not shared by the other which allow you to immediately conclude that the graphs are not isomorphic. As Ivan's answer states, the second graph has a pair of adjacent vertices of degree two and the first does not.

$\endgroup$
1
$\begingroup$

Usually it's better to look for a property of one graph that the other doesn't have. For example, Ivan Loh's answer. Another possibility is to count the number of $4$-cycles.

$\endgroup$
  • 1
    $\begingroup$ Another possibility is to count the $8$-cycles. The graph on the right is Hamiltonian, the graph on the left is not. $\endgroup$ – bof Nov 26 '13 at 13:22

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.