1
$\begingroup$

I just took an exam.

One of the open ended questions was to prove that two graphs are isomorphic. I set about proving that the mapping $$\phi : G \rightarrow H $$ is bijective. Let's assume I did that part of the question correctly.

Then, in order to show that adjacency and non-adjacency were preserved, I wrote out the adjacency matrix of each graph, and showed they were equal.

My Question

Is writing out the adjacency matrix of each graph and showing that they are equal enough to show that adjacency and non-adjacency are preserved? I am not concerned about how mathematically rigorous this is or isn't, considering most people in my class simply said "a cycle exists, and the vertices and edges are shared, so it is isomorphic."

I am concerned if it is mathematically sufficient to show adjacency and non-adjacency by showing that the adjacency matrices are the same. After all, with an adjacency matrix, we can see what is and is not adjacent, so is this a valid step in proving the graphs are isomorphic?

$\endgroup$
  • 3
    $\begingroup$ Yes, if you can label the vertices so as to make the adjacency matrices actually equal to each other, then that proves the graphs are isomorphic. $\endgroup$ – quasi Aug 2 '18 at 23:08
  • 1
    $\begingroup$ Checking that the adjacency matrices are the same is not only sufficient, it is also the definition of graph isomorphism. $\endgroup$ – angryavian Aug 2 '18 at 23:08
  • 1
    $\begingroup$ @angryavian Sure, if I take the transpose and what not. Otherwise, it is merely a part. I sought to show a bijection with the mapping of the vertices first, and then moved on to an adjacency matrix. $\endgroup$ – Prime Aug 2 '18 at 23:09
  • 1
    $\begingroup$ @quasi well yes, the vertices were labelled properly. So Thanks. $\endgroup$ – Prime Aug 2 '18 at 23:10
  • 1
    $\begingroup$ @Prime Yes: to be clear, I mean that showing that a given mapping $\phi : G \to H$ (of vertices to vertices) is an isomorphism is equivalent to showing that the adjacency matrices are the same. To show that two graphs are isomorphic, you have to produce this mapping, which is equivalent to finding an appropriate pairing/labeling of the vertices. $\endgroup$ – angryavian Aug 2 '18 at 23:18

Your Answer

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

Browse other questions tagged or ask your own question.