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?

---

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!

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.