Let $X$ be a connected graph, $T$ be a tree and $\phi: X \rightarrow T$ be a locally injective graph homomorphism. Prove that $\phi$ is injective!

Here, a graph means a pair of sets $X = (X^0,X^1)$ with three maps:

  • $\alpha: X^1 \rightarrow X^0$
  • $\omega: X^1 \rightarrow X^0$
  • $^\bar{}: X^1 \rightarrow X^1$

such that for any $e \in X^1$ the following holds

  • $\overline{\overline{e}} = e \neq \overline{e}$
  • $\alpha(e) = \omega(\overline{e})$

A graph homomorphism $\phi:X \rightarrow Y$ is a map from $X^0 \cup X^1$ to $Y^0 \cup Y^1$ such that

  • $\forall v \in X^0 \ \phi(v) \in Y^0$
  • $\forall e \in X^1 \ \phi(e) \in Y^1$
  • $\forall e \in X^1 \ \phi(\alpha(e)) = \alpha(\phi(e))$
  • $\forall e \in X^1 \ \phi(\omega(e)) = \omega(\phi(e))$
  • $\forall e \in X^1 \ \phi(\overline{e}) = \overline{\phi(e)}$

A graph homomorphism $\phi: X \rightarrow Y$ is locally injective if $\phi \restriction \star (x)$ is injetive $\forall x \in X^0$, where $\star(x) := \{e \in X^1 \ | \ \alpha(e) = x \}$.

A path between two vertices $v,\tilde{v} \in X^0$ is a sequence of edges $(e_1,e_2, \ldots, e_n) \in (X^1)^n$ such that

  • $\alpha(e_1) = v$, $\omega(e_n) = \tilde{v}$
  • $\forall 1 \le i < n \ \omega(e_i) = \alpha(e_{i+1})$

A graph $X$ is connected if for any pair of vertices $(v,\tilde{v}) \in (X^0)^2$ there is a path from $v$ to $\tilde{v}$.

I've tried to prove it via induction,but somehow seem to miss the property leading to my desired contradiction if I assume, $\phi$ was not injective. What goes wrong if I look at a path from $v$ to $\tilde{v}$ with $\phi(v) = \phi(\tilde{v})$ where either $v \neq \tilde{v}$ or the related edges are not equal?


$\DeclareMathOperator{\star}{\mathcal{star}}$ Ok, I got it. Let $v,\tilde{v} \in X^0$ with $\phi(v) = \phi(\tilde{v})$ and $(e_1,e_2, \ldots, e_n)$ be a reduced ($\forall i \ \overline{e_i} \neq e_{i+1}$) path from $v$ to $\tilde{v}$.

  • If $n = 0$, we have $v = \tilde{v}$ $\checkmark$
  • If $n = 1$, we have

    $\begin{eqnarray}\phi(\alpha (e_1)) &=& \alpha(\phi(e_1)) \\ &=& \alpha ( \phi \restriction_{\star(v)} (e_1)) \\ &=& \phi \restriction_{\star(v)} (\alpha(e_1))\\ &=& \phi(\omega(e_1)) \\ &=& \phi(\alpha(\overline{e_1}) \\ &=& \alpha(\phi(\overline{e_1})) \\ &=& \alpha ( \overline{\phi(e_1)}) \\ &=& \alpha( \overline{ \phi \restriction_{\star(v)} (e_1)}) \\ &=& \alpha (\phi \restriction _{\star(v)} (\overline{e_1})) \\ &=&\phi \restriction_{\star(v)} (\alpha(\overline{e_1})) \\ &=& \phi \restriction_{\star(v)} (\omega(e_1))\end{eqnarray}$

and hence (by the injectivity of $\phi \restriction{\star(v)}$): $v = \alpha(e_1) = \omega(e_1) = \tilde{v}$.

  • If $n > 1$, we get a path $(\phi(e_1), \phi(e_2), \ldots, \phi(e_n))$ from $\phi(v)$ to $\phi(\tilde{v})$ which (by our assumption $\phi(v) = \phi(\tilde{v})$) is a cycle and hence cannot be reduced. Fix $i \in \{1,\ldots,n-1\}$ with $\overline{\phi(e_i)} = \phi(e_{i+1})$. It is

    $\begin{eqnarray} \overline{\phi(e_i)} &=&\ \phi(\overline{e_i}) \\ &=& \phi \restriction_{\star({\alpha(e_{i+1})})}(\overline{e_i}) \\ &=& \phi \restriction_{\star({\alpha(e_{i+1})})}(e_{i+1}) \\ &=& \phi(e_{i+1})\end{eqnarray}$

and thus (by injectivity of $\phi \restriction _{\star(\alpha(e_{i+1}))}$): $\overline{e_i} = e_{i+1}$, which contradicts our assumption that $(e_1, \ldots, e_n)$ is reduced.

Therefore $\phi$ must be injective on the set of vertices.

Now fix $e,\tilde{e} \in X^1$ with $\phi(e) = \phi(\tilde{e})$. Then $\alpha (\phi(e)) = \phi(\alpha(e)) = \phi(\alpha( \tilde{e})) = \alpha ( \phi(\tilde{e}))$ which witnesses (by injectivity of $\phi$ on the set of vertices): $\alpha(e) = \alpha(\tilde{e})$, which implies $e, \tilde{e} \in \star(\alpha(e))$. Thus $\phi(e) = \phi \restriction _{\star(\alpha(e))} (e) = \phi \restriction _{\star(\alpha(e))} (\tilde{e}) = \phi(\tilde{e})$, which gives $e = \tilde{e}$ by injectivity of $\phi \restriction _{\star(\alpha(e))}$.


A cycle is a path from $v$ to $v$. Trees are connected graphs without (simple) cycles. You have built a cycle in $T$ but it is not necessarily simple. Try to get a simple (i.e. with all intermediate vertices different) cycle starting from the cycle you have.


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.