0
$\begingroup$

Let $\textbf{Grph}$ be the category whose objects are graphs $G = (V,E)$ such that $V$ is a set and $E \subseteq \mathcal{P}_2(V) := \{\{a,b\} \subseteq V: a\neq b\}$. We sometimes write $E(G)$ for $E$. The morphisms are maps $f:G\to H$ such that whenever $\{v,w\}\in E(G)$ then $\{f(v),f(w)\}\in E(H)$.

Do the notions of regular and extremal monomorphisms coincide in $\textbf{Grph}$?

$\endgroup$
5
$\begingroup$

The answer is yes.

It is clear that the extremal monomorphisms $(V_0, E_0) \to (V_1, E_1)$ are precisely the full graph embeddings, i.e. maps $f : V_0 \to V_1$ such that $f$ is injective and $(a, b) \in E_0$ if and only if $(f (a), f (b)) \in E_1$. It is also clear that regular monomorphisms are graph embeddings, so it remains to be shown that every full graph embedding is a regular monomorphism. But this is straightforward: given a graph $(V_1, E_1)$ and a full subgraph $(V_0, E_0)$, we can easily construct a graph $(V_2, E_2)$ containing two isomorphic copies of $(V_1, E_1)$ as full subgraphs whose intersection is isomorphic to $(V_0, E_0)$; then $(V_0, E_0)$ is the equaliser of the two embeddings $(V_1, E_1) \to (V_2, E_2)$.

$\endgroup$

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.