0
$\begingroup$

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)$?

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

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.