#### Howdy, Stranger!

It looks like you're new here. If you want to get involved, click one of these buttons!

Options

# Exercise 62 - Chapter 3

edited June 2018

We claim that there is exactly one graph homomorphism $$\alpha : G \rightarrow H$$ such that $$\alpha_{Arrow}(a) = d$$.

1. What is the other value of $$\alpha_{Arrow}$$, and what are the three values of $$\alpha_{Vertex}$$?
2. Draw $$\alpha_{Arrow}$$ as two lines connecting the cells in the ID column of $$G(Arrow)$$ to those in the ID column of $$H(Arrow)$$. Similarly, draw $$\alpha_{Vertex}$$ as connecting lines.
3. Check the source column and target column and make sure that the matches are natural, i.e. that “alpha-then-source equals source-then-alpha” and similarly for “target”. $$\begin{matrix} G := & & \begin{array}{c|cc} Arrow & source & target \\ \hline a & 1 & 2 \\ b & 2 & 3 \end{array} & & \begin{array}{c|} Vertex \\ \hline 1 \\ 2 \\ 3 \end{array} \\ H := & \begin{array}{c|cc} Arrow & source & target \\ \hline c & 4 & 5 \\ d & 4 & 5 \\ e & 5 & 5 \end{array} & & \begin{array}{c|} Vertex \\ \hline 4 \\ 5 \end{array} & \end{matrix}$$

• Options
1.
edited May 2018

The graph instances are offset so you can more easily complete the exercise.

Comment Source:The graph instances are offset so you can more easily complete the exercise.
• Options
2.
edited August 2018
1. Since $$\alpha_\mathrm{Arrow}(a)=d$$, it must also be the case that $$\alpha_\mathrm{Vertex}(1)=4$$ and $$\alpha_\mathrm{Vertex}(2)=5$$. Since $$b:2\to3$$, $$\alpha_\mathrm{Arrow}(b)$$ must start at $$5$$, the only such arrow in $$\mathcal{H}$$ is $$e$$. So, $$\alpha_\mathrm{Arrow}(b)=e$$ and $$\alpha_\mathrm{Vertex}(3)=5$$.

2. The first line in $$G(Arrow)$$ goes to the middle line of $$H(Arrow)$$, the second line of $$G(Arrow)$$ goes to the last line of $$H(Arrow)$$. The first line of $$G(Vertex)$$ goes to the first line of $$H(Vertex)$$, the last two lines of $$G(Vertex)$$ go to the last line of $$H(Vertex)$$.

3. $$s\circ\alpha_\mathrm{Arrow}(a)=s(d)=4=\alpha_\mathrm{Vertex}(1)=\alpha_\mathrm{Vertex}\circ s(a)$$. $$s\circ\alpha_\mathrm{Arrow}(b)=s(e)=5=\alpha_\mathrm{Vertex}(2)=\alpha_\mathrm{Vertex}\circ s(b)$$. $$t\circ\alpha_\mathrm{Arrow}(a)=t(d)=5=\alpha_\mathrm{Vertex}(2)=\alpha_\mathrm{Vertex}\circ t(a)$$. $$t\circ\alpha_\mathrm{Arrow}(b)=t(e)=5=\alpha_\mathrm{Vertex}(3)=\alpha_\mathrm{Vertex}\circ t(b)$$. So, the matches are natural.

Comment Source:1. Since \$$\alpha_\mathrm{Arrow}(a)=d\$$, it must also be the case that \$$\alpha_\mathrm{Vertex}(1)=4\$$ and \$$\alpha_\mathrm{Vertex}(2)=5\$$. Since \$$b:2\to3\$$, \$$\alpha_\mathrm{Arrow}(b)\$$ must start at \$$5\$$, the only such arrow in \$$\mathcal{H}\$$ is \$$e\$$. So, \$$\alpha_\mathrm{Arrow}(b)=e\$$ and \$$\alpha_\mathrm{Vertex}(3)=5\$$. 2. The first line in \$$G(Arrow)\$$ goes to the middle line of \$$H(Arrow)\$$, the second line of \$$G(Arrow)\$$ goes to the last line of \$$H(Arrow)\$$. The first line of \$$G(Vertex)\$$ goes to the first line of \$$H(Vertex)\$$, the last two lines of \$$G(Vertex)\$$ go to the last line of \$$H(Vertex)\$$. 3. \$$s\circ\alpha_\mathrm{Arrow}(a)=s(d)=4=\alpha_\mathrm{Vertex}(1)=\alpha_\mathrm{Vertex}\circ s(a)\$$. \$$s\circ\alpha_\mathrm{Arrow}(b)=s(e)=5=\alpha_\mathrm{Vertex}(2)=\alpha_\mathrm{Vertex}\circ s(b)\$$. \$$t\circ\alpha_\mathrm{Arrow}(a)=t(d)=5=\alpha_\mathrm{Vertex}(2)=\alpha_\mathrm{Vertex}\circ t(a)\$$. \$$t\circ\alpha_\mathrm{Arrow}(b)=t(e)=5=\alpha_\mathrm{Vertex}(3)=\alpha_\mathrm{Vertex}\circ t(b)\$$. So, the matches are natural.