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

Isomorphism in graphs

  1. Apr 22, 2010 #1
    Hi all,

    If I have to prove that the graph G and its complement G' are isomorphic, then is it enough to prove that both G and G' will have the same number of edges. Intuitively its clear to me, but how do I prove this. If there's a counterexample, please post.

    Thanks in advance.
  2. jcsd
  3. Apr 22, 2010 #2


    User Avatar
    Science Advisor

    That is certainly not enough. Consider the graphs of four vertices and three edges. They are not isomorphic to each of their complements.
    To prove an isomorphism you will need to define a function f : G --> G' such that an edge between [tex]v_1[/tex] and [tex]v_2[/tex] implies that there is an edge between [tex]f(v_1)[/tex] and [tex]f(v_2)[/tex].
  4. Apr 23, 2010 #3
    Oh yeah, I got the point.

    Thanks for the help.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook