# Locally injective graph homomorphism into a tree

$\DeclareMathOperator{\star}{\mathcal{star}}$

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?

## 2 Answers

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