The slides of my prof. say that two isomorphic graphs, with different labels are the same graph.

This must imply that the definition of a graph doesn't carry the nodes and vertices labels. Is this true ?

  • $\begingroup$ This depends on how you define a graph. $\endgroup$
    – Babelfish
    Aug 27 '18 at 12:11
  • 1
    $\begingroup$ The definition of a graph does "carry the node and vertex labels." Two graphs being isomorphic just means that you can switch the labels of one graph for the labels of the other, such that the graph "looks the same," i.e. has the same set of vertex-edge indices. Do a few examples if you're still confused. It should become clear. $\endgroup$
    – Dzoooks
    Aug 27 '18 at 12:14

That is very true and convenient.

Since two isomorphic graphs are basically the same graph we do not need to consider labeling into the definition of graph.

However, when we assign an adjacency matrix to a graph, labeling comes to play an important role because isomorphic graphs may have different adjacency matrices associated to them.


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.