I have to show the following:
- For the case that someone uses other definitions:
- $V$ is the set of the vertices of $G$
- $E$ is the set of $2$-element subsets of $V$ defined as $E \subseteq {V \choose 2} = \{\{x,y \}: x,y \in V, x \neq y \}$, i.e. the set of edges of $G$
- $N(v) = \{w \in V: \{v,w \} \in E \}$ is the neighborhood of $v$
Let $G = (V, E)$ and $G^{\ '} = (V^{'}, E^{'})$ be graphs. Show that a bijective function $f: V \to V^{'}$ is an isomorphism from $G$ to $G^{\ '}$, if for all $v \in V$ the following holds: $N(f(v)) = f(N(v))$.
I know that $f$ is an isomorphism, if for all $v,w \in V, v \neq w$ holds: $\{ v,w\} \in E \Leftarrow \Rightarrow \{ f(v), f(w)\} \in E^{'}$, so an edge $\{ v,w\}$ in $E$ is also an edge after aplying the function on $v$ and $w$.
From the definition of the neighborhood I know
- $N(f(v)) = \{f(w) \in V^{'}: \{f(v), f(w) \} \in E^{'} \}$. Here I get all $f(w)$ which make an edge with $f(v)$ in $E^{'}$.
- $f(N(v)) = f(\{w \in V: \{v,w \} \in E \ \})$. This are all $w$ which make an edge with $v$ in $E{'}$ BEFORE aplying the function.
Here I'm basically stuck to make a senseful statement/argument/reasoning how the equality for the neighborhoods implies the isomorphism.
If $\{v,w\}$ is an edge, then $w\in N(v)$, then $f(w)\in f(N(v))=N(f(v))$, then $\{f(v),f(w)\}$ is an edge. Conversely, if $\{f(v),f(w)\}$ is an edge, then $f(w)\in N(f(v))=f(N(v))$, then $f(w)=f(x)$ for some $x\in N(v)$. But as $f$ is objective, this means $x+v$, I i.e., $w\in N(v)$ and $\{v,w\}$ is an edge.