Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Difference between isomorphism and equality in graph theory?

  1. Jul 29, 2011 #1
    As the title suggest, I do not understand what the difference between isomorphism and equality is in terms of graph theory. I have tried searching the internet but the few definitions I could find for each did not really shed light on the difference. I know that an isomorphism is when there is a bijection between the two edge sets but I thought that is how set equality was defined also? Any help would be appreciated. Also, I do apologize if this is in the wrong section, perhaps it should have been in the set theory section...
  2. jcsd
  3. Jul 29, 2011 #2


    User Avatar
    Science Advisor

    In any area of mathematics, "Equality" of, say, A and B, means that A and B are just names for the same thing. If two graphs are "equal" then they are really the same graph.

    Saying that two mathematical structures are "isomorphic" means that all properties, that are defined for such structures, are the same. If I have, say, a graph, called "[itex]\alpha[/itex]", with two vertices, A and B, and the single edge beween A and B, and a graph, called "[itex]\beta[/itex]", with two vertices, X and Y, and the single edge between them, then those two graphs, [itex]\alpha[/itex] and [itex]\beta[/itex], are isomorphic, [itex]\alpha~ \beta[/itex], because the mapping A->X and B->Y also maps the single edge to the single edge. But they are not "equal" because they have different vertices- they are not the same graph.

    If, rather, I call the graph with vertices A and B and the single vertex [itex]\alpha[/itex] and then rename that same graph [itex]\beta[/itex], I can say [itex]\alpha= \beta[/itex] because "[itex]\alpha[/itex]" and "[itex]\beta[/itex]" are different names for the same thing.
    Last edited by a moderator: Jul 29, 2011
  4. Jul 29, 2011 #3
    Well, the only thing you need for isomorphism of two graphs G,G', other than their both having the same number of vertices and edges (in each connected component of the graph), is that the adjacency relation between the two is preserved by a function, i.e., if vertex vi is adjacent to vertex vj , then f should have f(vi) adjacent to f(vj). This last gives you some leeway. Easiest thing I can think of is , take a graph with 6 edges , and adjacency relation (vi,v_(i+1)) , i.e., v1 is adjacent to v2, which is adjacent to v3, etc. Now , rename the vertices by:

    G G'
    v1<-->v6 ,
    v2<-->v5 ,

    So now you see that, the adjacent pair (v1,v2) is sent to the adjacent pair (v5,v6) in G';
    and adjacency is preserved by f.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook