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$
7
  • $\begingroup$ What is the definition of an "isomorphism $f:V_1\to V_2$"? $\endgroup$
    – Casteels
    Commented Dec 15, 2013 at 12:59
  • $\begingroup$ It's a bijective morphism from V1 to V2. $\endgroup$ Commented Dec 15, 2013 at 13:01
  • 1
    $\begingroup$ And "bijective"? $\endgroup$
    – Casteels
    Commented Dec 15, 2013 at 13:01
  • $\begingroup$ Injective and surjective. $\endgroup$ Commented Dec 15, 2013 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$ Commented Dec 15, 2013 at 13:04

1 Answer 1

1
$\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$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .