Options

Exercise 62 - Chapter 3

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”.

Previous Next

Figure

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

Comments

  • 1.
    edited May 29

    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.
  • 2.
    edited August 6
    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.
Sign In or Register to comment.