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)
Link to originalgraph G {node[shape=point];x[xlabel="x"];y[xlabel="y"];y--x}then Edges-to-edges (2)
Link to originalgraph G {node[shape=point];x[xlabel="f(x)"];y[xlabel="f(y)"];y--x}in . -
takes non-edges to non-edges:
For all vertices in , if Non-edges-to-non-edges (1)
Link to originalgraph G {node[shape=point];x[xlabel="x"];y[xlabel="y"]}then Non-edges-to-non-edges (2)
Link to originalgraph G {node[shape=point];x[xlabel="f(x)"];y[xlabel="f(y)"]}in .