Let $\mathbf{Grf}$ be the category whose objects are small graphs and whose arrows are graph homomorphisms.

A small graph is tuple $G = \langle V, E, \operatorname{src}, \operatorname{trg}\rangle$ where $V$ and $E$ are sets, and $\operatorname{src},\operatorname{trg}\colon E \to V$ are functions.

Let $G_1 = \langle V_1, E_1, \operatorname{src}_1, \operatorname{trg}_1\rangle$ and $G_2 = \langle V_2, E_2, \operatorname{src}_2, \operatorname{trg}_2\rangle$ be two graphs. A graph homomorphism $h\colon G_1 \to G_2$ is a pair of functions $h_0\colon V_1 \to V_2$ and $h_1\colon E_1 \to E_2$ such that

$$ \operatorname{src}_2 \circ h_1 = h_0 \circ \operatorname{src}_1 \qquad\text{and}\qquad\operatorname{trg}_2 \circ h_1 = h_0 \circ \operatorname{trg}_1 $$

Is $\mathbf{Grf}$ a concrete category?

I would say yes,and here it is my solution: Let $U\colon\mathbf{Grf}\to\mathbf{Set}$ be the functor defined by

$$ UG = V\uplus E = (V \times \{0\}) \cup (E \times \{1\}) $$ and

$$ (Uh)(x,i) = \begin{cases} h_0(x) & \text{if $i = 0$}\\ h_1(x) & \text{if $i = 1$} \end{cases} $$

The functor $U$ is faithful: Let $f,g\colon G_1 \to G_2$ be two graph homomorphisms. If $Uf = Ug$, then $(Uf)(v, 0) = f_0(v) = g_0(v) = (Ug)(v, 0)$ for each $v \in V$ and $(Uf)(e, 1) = f_1(e) = g_1(e) = (Ug)(e, 1)$ for each $e \in E$, and therefore $f = g$.

Is this solution correct?

If yes, there are other simpler solutions?

  • 1
    $\begingroup$ Yes, it's correct. This is basically what has to be done, I don't see any simpler way.. $\endgroup$ – Berci Feb 21 '19 at 15:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.