Pullback in the category of graphs

Question

Consider the category of (undirected) multigraphs (possibly with loops) and multigraph homomorphisms. What are pullbacks in such a category? Is there an informal, colloquial and intuitive way to describe them?

According to the definition of pullback, given the multigraphs $G_1 = (V_1, E_1, r_1)$, $G_2 = (V_2, E_2, r_2)$ and $G$ and two multigraph morphisms $h_1 \colon G_1 \to G$ and $h_2 \colon G_2 \to G$, the pullback of $h_1$ and $h_2$ exists and (I guess) should be a multigraph $G'$ whose vertices are couples $(v_1,v_2) \in V_1 \times V_2$ and whose edges are couples $(e_1, e_2) \in E_1 \times E_2$ such that their components are identified via $h_1$ and $h_2$, i.e. $h_{1_V}(v_1) = h_{2_V}(v_2)$ and $h_{1_E}(e_1) = h_{2_E}(e_2)$.

But what does it mean intuitively? What does $G'$ look like? It seems to me that $G'$ sounds like the "minimal" multigraph "compatible" with $h_1$ and $h_2$, but I am not sure this informal explanation makes sense.

I guess I can find more information in the reference suggested in the accepted answer of this question, but I cannot access it.

---

Context.

An (undirected) multigraph (possibly with loops) is a triple $G = (V,E,r)$ where $V$ is the set of vertices, $E$ is the set of edges, and $r \colon E \to \{ \{v,w\} \mid v,w \in V\}$ associates every edge with its two endpoints (possibly they coincide).

Given two multigraphs $G = (V, E, r)$ and $G' = (V', E', r')$, a multigraph homomorphism $h \colon G \to G'$ is a couple $h = (h_V \colon V \to V', h_E \colon E \to E')$ of functions that "preserve edges", i.e. such that if $r(e) = \{v,w\}$ then $r'(h_E(e)) = \{h_V(v), h_V(w)\}$.

Answer 1

Simple Graphs

By way of example, suppose we consider the category of simple graphs; i.e., objects are sets along with binary relations and arrows are functions preserving relationships.

Let us write $V(X)$ for the (vertex) set of an object $X$, and $E(X)$ for its binary (edge-adjacency) relation.

---

Then, the pullback of $f : A → C ← B : g$ is the graph $A \times_C B$ with set $V(A \times_C B) = \{(a, b) | f\, a = g\, b\} = V(A) \times_{V(C)} V(B)$ and its relation is $E(A \times_C B) = E(A) \times E(B)$ where relation multiplication means $(a, a′) \;(R × S)\; (b, b′) \quad≡\quad a \,R\, a′ \;∧\; b\,S\,b′$.

What are the remaining pieces of the pullback construction?

The usual projections are readily shown to be graph morphisms, and the mediating arrow for any given $h, k$ is $z ↦ (h\, z, k\, z)$, thereby completing the requirements of the construction... Exercise: Work out the details.

---

Pullbacks form intersections of subobjects

That is, the pullback [above] is obtained by forming the ‘intersection’ [loosely, as discussed below] of vertices, and keeping whatever edges that are in the intersection.

In general, if we think of $f : A → C ← B : g$ as identifying when two elements are the ‘same’ ---i.e., “a and b are similar when the f-feature of $a$ is the same as the g-feature of $b$”--- then the pullback yields the ‘intersection’ upto this similarity relationship. For a honest-to-goodness equivalence relationship, one considers ‘equalisers’

---

Moreover, say a graph $X$ is ‘complete’ when $E(X) ≅ V(X) \times V(X)$, then it can be quickly shown that if $A$ and $B$ are complete graphs then so is their pullback; thus the category of complete simple graphs also has pullbacks.

---

Concrete Example

Consider the following graphs: $A = •_1 → •_2 → •₃$ and $B = •₄ → •₅ → •₆$ and $C = •₇ →_→ \substack{•₈ \\ •₉} →_→ •₁₀$ ---here $C$ has two arrows from 7, one to 8 and one to 9, which each have an arrow to 10; drawing is hard!

Let $f = \{1 ↦ 7, 2 ↦ 8, 3 ↦ 10\}, g = \{4 ↦ 7, 5 ↦ 9, 6 ↦ 10\}$; ---i.e., $A$ sits on the top part of $C$ while $B$ sits on the bottom part.

Exercise: Form their pullback!

Then their pullback [‘intersection’] is the empty graph on 2 vertices $\substack{• \\ (1, 4)} \quad \substack{• \\ (3, 6)}$ ---i.e., the part of C that both A and B sit over.

Notice that $A, B, C$ are all connected whereas their pullback is not; as such, the category of connected simple graphs doesn't have pullbacks.

Answer 2

Your intuition that the pullback "sounds like the "minimal" (actually maximal) compatible multigraph is true, and in fact is true in many more cases.

This is because the pullback of $X\xrightarrow{f}Z\xleftarrow{g}Y$ in any category is the equalizer of the parallel pair $X\times Y \rightrightarrows Z$ given $f\circ\text{pr}_X$ and $g\circ\text{pr}_Y$.

Specializing to your case of multigraphs:

• the product of $G_1 = (V_1,E_1,r_1)$ and $G_2 = (V_2,E_2,r_2)$ is $(V_1\times V_2,E_1\times E_2,r_1\times r_2)$
• the equalizer of a parallel pair $f,g:G_1\rightrightarrows G_2$ is the maximal subgraph of $G_1$ where $f=g$

Combining these two, we get

• the pullback of $G_1\xrightarrow{f}G\xleftarrow{g}G_2$ isthe maximal subgraph of $(V_1\times V_2,E_1\times E_2,r_1\times r_2)$ where $f\circ\text{pr}_{G_1}$ and $g\circ\text{pr}_{G_2}$