Graphs and are isomorphic if there is an isomorphism between them: A function from the vertices of to the vertices of such that:

  • is a bijection (function)

  • takes edges to edges:

    For all vertices in , if

    Edges-to-edges (1)

    graph G {node[shape=point];x[xlabel="x"];y[xlabel="y"];y--x}
    Link to original
    then

    Edges-to-edges (2)

    graph G {node[shape=point];x[xlabel="f(x)"];y[xlabel="f(y)"];y--x}
    Link to original
    in .
  • takes non-edges to non-edges:

    For all vertices in , if

    Non-edges-to-non-edges (1)

    graph G {node[shape=point];x[xlabel="x"];y[xlabel="y"]}
    Link to original
    then

    Non-edges-to-non-edges (2)

    graph G {node[shape=point];x[xlabel="f(x)"];y[xlabel="f(y)"]}
    Link to original
    in .