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

Proving a (known isomorphic) graph is isomorphic

  1. Nov 28, 2017 #1
    1. The problem statement, all variables and given/known data
    Included as an upload or:

    The graph is isomorphic.

    Prove that it is indeed isomorphic.

    2. Relevant equations

    3. The attempt at a solution
    Let the left graph be G(Vg,Eg), and the right graph be H(Vh,Eh)

    Since the graph is isomorphic we know:
    1) There is a bijective function f from Vg to Vh with the property that a and b are adjacent in G iff f(a) and f(b) are adjacent in H for all a,b in Vg.
    2) The graphs share the same number of vertices, edges, and degree sequence.

    And then from here I'm lost. I know that I have to formulate a bijective function from Vg to Vh which is easy since the cardinality of vertices are the same. The issue I have is being sure that this bijective function has the second property (a and b are adjacent in G iff f(a) and f(b) are adjacent in H for all a,b in Vg).

    Given that I know the graph is isomorphic, is there any methodical approach to this? I tried messing around with various functions for about 3 hours before I found one that worked. However, there was no method to my madness beyond trial and error.

    With simpler graphs, I can kind of tell how the bijective function should be formed because I can visualize a form of the graph that both graphs fit into. For example I can see that a star -- like in graph g -- can unfold into a cycle of 5 vertices (or a pentagon). But as these get more complex I can't. Even breaking the graph into more manageable chunks doesn't seem to help. I'm worried that I won't have enough time to figure these out on a test.


    Attached Files:

  2. jcsd
  3. Nov 28, 2017 #2


    Staff: Mentor

    What does this mean? Isomorphism is a comparison of two things. I can't tell what is given here, but the problem seems to be to show that the first graph is isomorphic to the second graph.
    Since the two graphs are isomorphic ...
    One technique is to set up an n x n adjacency matrix. If node a is adjacent to node b, put a 1 in the appropriate cell of the matrix, at the row for a and the column for b. Necessarily the (b, a) element of the matrix will be 1, since node a being adjacent to node b means that node b is adjacent to node a.
    What does "degree sequence" mean? Does it mean how many edges intersect at a node? If so, you could capture this information in an array of length n, with the first element of the array being how many edges are connected to node a, and so on through the nodes of each graph.
  4. Nov 28, 2017 #3


    User Avatar
    Science Advisor
    Gold Member

    Why is it difficult? Use the two degree sequences -- of the respective graphs -- to do the "relabeling" . If g has degree n in G , then find g' with degree n in G' , making sure adjacencies are preserved.
  5. Nov 28, 2017 #4
    This is correct.

    This is how you do the second part of the proof, which is what I'm having trouble with. The bijection is easy for me to spot, but for the adjacency matrix you have to arrange your rows and columns in such a manner that it produces identical matrices for each graph. In this particular case I am having trouble because each vertex has the same number of adjacent vertices. So producing the matrix resulted in trial and error, and I don't think I'd have enough time (on a test) to do this since it took me ~3 hours for this problem. And this particular problem would be be a pretty standard test question for this professor.

    This is what a degree sequence is. For example if the left graph is graph "G" then we have
    deg(u1) = deg(u2) = deg(u3) = ... = deg(u9) = deg(u10) = 3.

    Thus the degree sequence of G is 3,3,3,..,3 (ten times).

    I wouldn't say it's difficult. I'd say it's time consuming. As aforementioned it took me 3 hours to get this one.

    In this particular case the issue is that each vertex g has a degree of 3 in G. This means your bijective function has 10! (factorial) different possibilities -- which makes preserving the adjacencies difficult to do efficiently (for the sake of a test). In the case of managing the adjacencies, each vertex has 3 possible paths to potentially preserve its structure.
  6. Nov 28, 2017 #5


    User Avatar
    Science Advisor
    Gold Member

    Isn't there a result on graphs with identical degree sequence being isomorphic?
  7. Nov 28, 2017 #6
    Not that I'm aware of. The reason you check for degree sequence is that in order for it to be an isomorph they must have the same degree sequence. However, having the same degree sequence does not make them isomorphs. For example you could have a connected cyclic graph where n = 8, and another graph of two cycles with n = 4. In this case both graphs would be bipartite, share the same degree sequence, share the same number of vertices, and the same number of edges -- but they are not isomorphs because one is disconnected and the other is connected.

    Typically you check the degree sequence, number of edges, whether they are bipartite, the girth, and the number of vertices to check whether or not it's reasonable to assume the graphs are isomorphs. The only way is prove it (as of our current understanding in the class -- and that I'm aware of) is to produce the bijective function.
  8. Nov 28, 2017 #7


    User Avatar
    Science Advisor
    Gold Member

    FWIW Graph isopmorphism, from a computational standpoint is a tough problem, generally viewed as being a bit tougher than prime factoring, but not 'quite' NP-Complete.

    Sometimes you can reject a claim of graph isomorphism based on spectral properties of the Adjacency Matrices. The first graph in your exercise is a Petersen Graph. This motivates a fun spectral result that "Three Petersens are not Enough" to tile / create a complete graph.

    Note: this is available as miniature 13 and 14 of Thirty Three Miniatures, a preliminary version of which is available for free at the author's website, here:

    http://kam.mff.cuni.cz/~matousek/la-ams.html and then clicking "preliminary version on-line"

    (note: to moderators: see the root page here: http://kam.mff.cuni.cz/~matousek/ )

    - - - - -
    I'm not sure I have any advice on how to do this problem more quickly by hand, though.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Have something to add?