# Graph isomorphism

The definition for graph isomorphism states that two graphs $G_1 = (V_1,E_1)$, $G_2 = (V_2,E_2)$ are isomorphic if there is an isomorphism $f:V_1\to V_2$ such as each $u$ and $v$ vertex from $V_1$ are adjacent in $G_1$ if and only if $f(u)$ and $f(v)$ are adjacent in $G_2$.

Does this mean that we can have isolated nodes in one graph? But wouldn't that mean that the isolated nodes aren't mapped to anything by the $f$ function => contradiction, because $f$ is bijective?

Does this mean that $\operatorname{card}(V_1) \ne \operatorname{card}(V_2)$?

• What is the definition of an "isomorphism $f:V_1\to V_2$"? – Casteels Dec 15 '13 at 12:59
• It's a bijective morphism from V1 to V2. – Silent Control Dec 15 '13 at 13:01
• And "bijective"? – Casteels Dec 15 '13 at 13:01
• Injective and surjective. – Silent Control Dec 15 '13 at 13:02
• So basically V1 and V2 have the same number of elements? I was tricked by the fact that the function maps edge to edge. – Silent Control Dec 15 '13 at 13:04

The definition of graph isomorphism is that: two graphs $G_1$ and $G_2$ are isomorphic if there is a function $f: V(G_1) \rightarrow V(G_2)$ that is bijective and that preserves adjacency and nonadjacency. Thus, to say a bijection $f$ between vertex sets is an isomorphism is equivalent to saying $uv \in E(G_1)$ iff $f(u)f(v) \in E(G_2)$. The map $f$ on vertices induces a map on the 2-subsets of vertices by the rule $f: (u,v) \mapsto (f(u),f(v))$, and this induced map would map the edge set of $G_1$ to the edge-set of $G_2$, i.e. $f(E(G_1))=E(G_2)$. Of course, since $f$ is bijective, the two graphs would have the same number of vertices. Furthermore, a vertex having $k$ neighbors in $G_1$ is mapped to a vertex in $G_2$ that again has $k$ neighbors since edges incident (and vertices adjacent) to a vertex $v \in V(G_1)$ are mapped to edges incident (and vertices adjacent) to $f(v)$. Thus, isolated vertices are mapped to isolated vertices, and a vertex of degree $k$ is mapped to a vertex of degree $k$, and so on.