Pullback in the category of graphs

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

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.