1.3.9 Example In the same spirit as Example 1.3.8, let us see what data type is represented by the graph

a s

−→−→t n (1.4)

The data type has a signature consisting of two objects, call thema and n, and two arrows, let us call them (temporarily) s,t: a−→ n. But if we interpreta as arrows, n as nodes and s and t as source and target, this is exactly what we have defined a small graph to be: two sets and two functions from one of the sets to the other. For this reason, this graph is called the graph of graphs. (See [Lawvere, 1989].)

1.3.10 Exercises

1. The graphs in this section have labeled nodes; for example, the two nodes in (1.3) are labeled ‘1’ and ‘n’. Produce a graph analogous to (1.4) that expresses the concept of ‘graph with nodes labeled from a setL’.

2. LetG be a graph with set of nodesN and set of arrowsA. Show thatG is simple if and only if the functionhsource,targeti:A−→N×N is injective.

(This uses the pair notation for functions to products as described in 1.2.8.)

### 1.4 Homomorphisms of graphs

A homomorphism of graphs should preserve the abstract shape of the graph.

A reasonable translation of this vague requirement into a precise mathemat-ical definition is as follows.

1.4.1 Definition A homomorphismφ from a graph G to a graph H, denotedφ:G −→H, is a pair of functionsφ0:G0−→H0andφ1:G1−→H1

with the property that ifu:m−→n is an arrow of G, then φ1(u) :φ0(m)

−→φ_{0}(n) inH.

It is instructive to restate this definition using the source and target
mappings from 1.3.9: let sourceG :G1−→G0 be the source map that takes
an arrow (element ofG1) to its source, and similarly define target_{G}, sourceH

and target_{H}. Then the pair of mapsφ_{0}:G_{0}−→H_{0} andφ_{1}:G_{1}−→H_{1}is a
graph homomorphism if and only if

source_{H} ^{◦}φ1=φ0^{◦}source_{G}
and

target_{H} ^{◦}φ1=φ0^{◦}target_{G}

1.4.2 Notation of the form a: B −→C is overloaded in several ways. It can denote a set-theoretic function, a graph homomorphism or an arrow in a graph. In fact, all three are instances of the third since there is a large graph whose nodes are sets and arrows are functions (see 1.3.3) and another whose nodes are (small) graphs and arrows are graph homomorphisms.

Another form of overloading is that if φ :G −→ H is a graph
homo-morphism, φ actually stands for a pair of functions we here call φ_{0} : G_{0}

−→H0 and φ1:G1−→H1. In fact, it is customary to omit the subscripts and useφfor all three (the graph homomorphism as well as its components φ0 andφ1).

This does not lead to ambiguity in practice; in reading about graphs you are nearly always aware of whether the author is talking about nodes or arrows. We will keep the subscripts in this section and drop them thereafter.

1.4.3 Example IfG is any graph, theidentity homomorphismid_{G} :G

−→G is defined by (id_{G})0= id_{G}_{0} (the identity function on the set of nodes
ofG) and (id_{G})1= id_{G}_{1}.

1.4.4 Example IfG is the graph

1 -2 -3

4

?

R

(1.5)

andH is this graph,

S -F

Q

?

R

I (1.6)

then there is a homomorphism φ:G −→H for whichφ0(1) =S, φ0(2) =
φ0(3) =F and φ0(4) =Q, andφ1 takes the loop on 2 and the arrow from
2 to 3 both to the upper loop onF; what φ1does to the other two arrows
is forced by the definition of homomorphism. Because there are two loops
onF there are actually four possibilities forφ_{1}on arrows (while keepingφ_{0}
fixed).

1.4 Homomorphisms of graphs 13 1.4.5 Example IfH is any graph with a node nand a loopu:n−→n, then there is a homomorphism from any graph G to H that takes every node of G to n and every arrow to u. This construction gives two other homomorphisms fromG toH in Example 1.4.4 besides the four mentioned there. (There are still others.)

1.4.6 Example There is a homomorphism σ from Example 1.3.8 to the graph of sets that takes the node called 1 to a one-element set, which in contexts like this we will denote{∗}, and that takes the nodento the setN ofnatural numbers. (Following the practice in computing science rather than mathematics, we start our natural numbers at 0.) The homomorphism σtakes the arrow 1−→nto the function∗ 7→0 that picks out the natural number 0, andσ(succ), naturally, is the function that adds 1. This is an ex-ample of a model of a sketch, which we discuss in 4.7.7. This homomorphism gives a semantics for the sketch constituted by the abstract graph of 1.3.8.

1.4.7 Example The homomorphism in Example 1.4.6 is not the only homo-morphism from Example 1.3.8 to sets. One can letngo to the set of integers (modk) for a fixedkand let succbe the function that adds one (modk) (it wraps around). You can also get other homomorphisms by taking this ex-ample (or 1.4.6) and adjoining some extra elements to the set corresponding tonwhich are their own successors.

1.4.8 Example Example 1.3.9 can be given a semantics in the same way
as Example 1.3.8. IfG isany small graph, there is a graph homomorphism
φfrom the diagram in (1.4) to the graph of sets for which φ0(n) is the set
of nodes of G, φ_{0}(a) is the set of arrows, and φ_{1} takes the arrows labeled
source and target to the corresponding functions from the set of arrows of
G to the set of nodes ofG.

Moreover, the converse is true: any homomorphism from (1.4) to the
graph of sets gives a graph. The nodes of the graph are the elements ofφ_{0}(n)
and the arrows are the elements ofφ_{0}(a). Iff ∈φ_{0}(a), then the source off
isφ1(source)(f) and the target isφ1(target)(f). Thus the graph of
Exam-ple 1.3.2 corresponds to the homomorphismφwhereφ0(n) ={1,2},φ0(a) =
{a, b, c},φ1(source) is the functiona7→1, b7→1, c7→2 andφ1(target) is the
functiona7→1, b7→2, c7→1.

In short, graph homomorphisms from (1.4) to the graph of sets corre-spond to what we normally call graphs.

1.4.9 Notation In an expression like ‘φ_{1}(source)(f)’,φ_{1}is a function whose
value at ‘source’ is a function that applies to an arrowf. As this illustrates,
the application operation associates to the left.

1.4.10 Exercises

1. Show that if the codomainH of a graph homomorphism φ is a simple graph, thenφ1is determined uniquely byφ0.

2. Show that the composite of graph homomorphisms is a graph
homo-morphism. Precisely: if φ: G −→H and ψ :H −→K are graph
homo-morphisms, then define the compositeψ ^{◦}φ by requiring that (ψ ^{◦}φ)0=
ψ0 ^{◦}φ0 and (ψ ^{◦}φ)1=ψ1 ^{◦}φ1. Then prove that ψ ^{◦}φ is a graph
homo-morphism.

3. Letφbe a homomorphismG −→H for which bothφ0andφ1are bijective.

Defineψ:H −→G byψ0= (φ0)^{−1}andψ1= (φ1)^{−1}.
a.Show thatψis a graph homomorphism fromH toG.

b.Using the definition of composite in the preceding exercise, show that
bothψ^{◦}φ= id_{G} andφ^{◦}ψ= id_{H}.