$\begingroup$
This is an excerpt from Diestel's book and I'd like to clarify the following moment.
Suppose that $\varphi:V\to V'$ is a graph homomorphism and $x'\in \operatorname{Im}\varphi$ then $\varphi^{-1}(x')\neq \varnothing$. I'd like to show that $\varphi^{-1}(x')\subseteq V$ is independent set of vertices. If $v_1,v_2\in \varphi^{-1}(x')$ then $\varphi(v_1)=\varphi(v_2)=x'$. If $v_1,v_2$ are adjacent then $\{\varphi(v_1),\varphi(v_2)\}=\{x'\}\in E'.$
But I do not see the contradiction. What is wrong?
$\endgroup$1 Answer
$\begingroup$$\{ \varphi(v_1),\varphi(v_2)\}$ cannot be an edge of $G'$ because it is a set that has only one element.
$\endgroup$ 15
