Graph Isomorphism

Isomorphism of Graphs

Two simple graphs $G_1=(V_1,E_1)$ and $G_2=(V_2,E_2)$ are isomorphic if there exists a bijective function $f$ from $V_1$ to $V_2$ with the property that $a$ and $b$ are adjacent in $G_1$ if and only if $f(a)$ and $f(b)$ are adjacent in $G_2$, for all $a$ and $b$ in $V_1$. Such a function is called an isomorphism. Two simple graphs that are not isomorphic are called non-isomorphic.

Invariants under Isomorphism

• Number if vertices
• Number of edges
• Number of vertices of each degree
• The existence of a simple circuit of length $k$, where $k$ is a positive integer greater than $2$. If any of these quantities differ in two simple graphs, these graphs cannot be isomorphic.