Isomorphism¶

Necessary conditions for two graphs to be isomorphic:¶

• They must have the same number of vertices

• They must have the same number of edges

• Their vertices must have matching degrees (same degree sequence)

def is_isomorphic(graph1, graph2):
    # Check number of vertices
    if len(graph1.nodes) != len(graph2.nodes):  # If number of vertices isn't equal
        return False

    # Check number of edges
    if len(graph1.edges) != len(graph2.edges):  # If number of edges isn't equal
        return False

    # Check degree sequences
    if sorted(graph1.degrees) != sorted(graph2.degrees):  # Compare sorted degree lists
        return False

    # More detailed checks needed for full verification
    return True

Identical Graphs¶

Consider graphs G and H. If V(G) = V(H) and E(G) = E(H), then we say graphs G and H are identical.

Isomorphism¶

Consider graphs G and H. We define a bijective function f(u) that maps each vertex u in graph G to a corresponding vertex in graph H, with the condition that f(u) and f(v) are equal only if u equals v.

If we can construct a function f between the vertices of G and H such that replacing each vertex u in graph G with f(u) makes the two graphs identical, we say the graphs are isomorphic.

In other words, an edge uv exists in G if and only if the edge f(u)f(v) also exists in H; in this case, the two graphs are isomorphic.

Automorphism¶

A simple definition of an automorphism is a graph morphism to itself. That is, by permuting the vertices of the graph, the edge set remains unchanged.