## Franklin's Notes

### Categories of graphs

The following are commonly used categories whose objects are graphs:

• $\mathsf{SimpGph}$ has simple graphs (i.e. graphs without loops or multiple edges) as its objects, and edge-preserving functions as its morphisms.

• $\mathsf{Dgr}$ has simple directed graphs as its objects and edge-preserving functions as its morphism.

One might ask to what extent simple graphs and directed graphs can be "encoded" in terms of each other. That is, are there ways of expressing simple graphs as directed graphs or directed graphs as simple graphs in ways that preserve their symmetries to a great extent?

Proposition 1. There exists a full and faithful functor $F:\mathsf{SimpGph}\to\mathsf{Dgr}$.

Proof. Simply consider the functor that maps each simple graph to a digraph by replacing each edge between a pair of vertices with the two directed edges between those pairs of vertices. $\blacksquare$

This is not much of a surprise, since simple graphs "contain less information" than directed graphs in a manner of speaking. But what about the other way around? The question of how best to represent directed graphs as simple graphs is much less obvious.

Conjecture 1. There exists no full and faithful functor $F:\mathsf{Dgr}\to\mathsf{SimpGph}$.

Proposition 2. There exists a faithful functor $F:\mathsf{Dgr}\to\mathsf{SimpGph}$ that reflects and creates isomorphisms.

Proof. Suppose $G=(V,E)$ is a given digraph. We will describe a functor $F:\mathsf{Dgr}\to\mathsf{SimpGph}$ by defining the image $FG$ for every graph $G\in \mathsf{Dgr}$. Let $FG = (V',E')$ where $V'=V\times 4 \cup 14$. The vertices in $V'$ will be partitioned into $6$ subsets, according to this image:

The vertex subsets $V_1,V_2,V_3,V_4$ are equal to $V\times{1},V\times{2},V\times{3},V\times{4}$ respectively, and the additional $14$ vertices are used in $V_5$ and $V_6$, which receive $6$ and $8$ vertices respectively. Edges are drawn according to the following rules:

• The vertices of $V_5$ and $V_6$ are connected by edges as shown in the image above.
• Every vertex in $V_1$ has an edge adjoining it to the pictured vertex of $V_5$ (with many edges emanating from it)
• Every vertex in $V_4$ has an edge adjoining it to the pictured vertex of $V_6$
• Every vertex $(v,2)\in V_2$ is joined to $(v,1)\in V_1$
• Every vertex $(v,3)\in V_3$ is joined to $(v,2)\in V_2$
• Every vertex $(v,4)\in V_4$ is joined to $(v,3)\in V_3$
• The vertex $(v,1)\in V_1$ is joined to $(w,4)\in V_4$ if and only if $(v,w)\in E$, that is, if $(v,w)$ is one of the directed edges of the original digraph $G$.

So we have defined the action of $F$ on the objects of $\mathsf{Dgr}$. Now we must define its action on the morphisms. If $f:G=(V,E)\to H=(W,D)$ is a homomorphism of directed graphs, then we define $Ff$ as the morphism which sends the elements of $V_5$ and $V_6$ to the corresponding elements of $W_5$ and $W_6$, and sends and it is simple to verify that this is, in fact, a graph homomorphism $Ff:FG\to FH$. Faithfulness is also easy to verify, for if $f_1,f_2$ are distinct morphisms in $\mathsf{Dgr}$, then there exists $v$ such that $f_1(v)\ne f_2(v)$, meaning that $(Ff_1)((v,1))\ne (Ff_2)((v,1))$ and hence $Ff_1\ne Ff_2$.

Now we show that $F$ creates isomorphisms - that is, if $FG$ and $FH$ are isomorphic in $\mathsf{SimpGph}$, it follows that $G$ and $H$ are isomorphic in $\mathsf{Dgr}$. Suppose that $f':FG\to FH$ is an isomorphism. By inspecting the structure of the constructed graph, we may see that the only cycles of odd lengths are the triangle in $V_5$ and the pentagon in $V_6$. We may conclude that $f$ sends corresponding vertices of $V_5$ and $V_6$ onto corresponding vertices of $W_5$ and $W_6$ respectively. The vertices of $V_1,V_2,V_3,V_4$ can also be characterized as follows:

• The $V_1$ vertices are precisely those which are not in $V_5$ but which are adjacent to a vertex in $V_5$
• The $V_4$ vertices are precisely those which are not in $V_6$ but which are adjacent to a vertex in $V_6$
• The $V_2$ vertices are precisely those which are not in $V_4$ or $V_5$ but which are adjacent to a vertex in $V_1$
• The $V_3$ vertices are precisely those which are not in $V_1$ or $V_6$ but which are adjacent to a vertex in $V_4$

This means that $f'$ must send vertices in $V_1,V_2,V_3,V_4,V_5,V_6$ to vertices in $W_1,W_2,W_3,W_4,W_5,W_6$ respectively, since it is an isomorphism. Now we are ready to define an isomorphism $f:G\to H$: simply let $f(v)=w$ iff $f'((v,1))=(w,1)$, which is a valid definition because we know that $f'$ maps vertices in $V_1$ to vertices in $W_1$. We also have that

• $f$ is surjective, because $f'$ is surjective, meaning that for every $w\in W$, the vertex $(w,1)\in W_1$ has a preimage $(v,1)\in V_1$, so that $f(v)=w$.
• $f$ is injective, because $f'$ is injective: if $f$ mapped two vertices onto the same vertex, then so would $f'$, which is impossible since it's an isomorphism.
• We have $f'((v,1))=(f(v),1)$ by definition, but we also have that $f'((v,4))=(f(v),4)$. This is because $(v,4)$ is the unique vertex in $V_4$ which is connected to $(v,1)$ via a path that consists of a $(v,1)$ followed by a vertex in $V_2$ followed by a vertex in $V_3$ followed by a vertex in $V_4$, and $(f(v),4)$ is the unique vertex in $W_4$ that is connected to $(f(v),1)$ via a path that consists of $(f(v),1)$ followed by a vertex in $W_2$ followed by a vertex in $W_3$ followed by a vertex in $W_4$. Since $f$ respects the partitions $V_i,W_i$, it must preserve this relationship, meaning that since $(v,4)$ and $(f(v),4)$ are the unique vertices with this relationship to $(v,1)$ and $f'((v,1))=(f(v),1)$, they must map onto each other under isomorphism, and $f'((v,4))=(f(v),4)$ as claimed.
• $f$ preserves adjacency and non-adjacency. That is, there exists a directed edge from $v_1$ to $v_2$ in $G$ iff there exists a directed edge from $f(v_1)$ to $f(v_2)$ in $H$. The reasoning goes as follows: if there exists a directed edge from $v_1$ to $v_2$ in $G$, then there is an edge between $(v_1,1)$ and $(v_2,4)$ in $FG$ (by the definition of $F$), meaning that there is an edge between $f'((v_1,1))=(f(v_1),1)$ and $f'((v_2,4))=(f(v_2),4)$ in $FH$, and so there is a directed edge from $f(v_1)$ to $f(v_2)$ in $H$. Similar reasoning proves the converse direction.

From the isomorphism $f':FG\to FH$, we have constructed an isomorphism $f:G\to H$, showing that our functor $F$ creates isomorphisms.

We can similarly show that $F$ reflects isomorphisms, or that $f:G\to H$ is an isomorphism whenever $Ff$ is an isomorphism. If $Ff:FG\to FH$ is an isomorphism, clearly it must send each vertex in $V_i$ to a vertex in the corresponding $W_i$, and it must do so injectively and surjectively, as explained above. Because of how $Ff$ is defined piecewise on the $V_i$, it follows that $f$ must be both injective and surjective. If $f$ were not an isomorphism, then there would necessarily exist some $v_1,v_2$ such that there is no directed edge from $v_1$ to $v_2$ in $G$ but there is a directed edge from $f(v_1)$ to $f(v_2)$ in $H$. But this would mean that $(v_1,1)$ and $(v_2,4)$ would be nonadjacent in $FG$ while $f((v_1,1))$ and $f((v_2,4))$ would be adjacent in $FH$, contradicting the fact that $Ff$ was postulated to be an isomorphism. Hence, we have that $F$ reflects isomorphisms. $\blacksquare$

Note that the functor $F$ described in the above proof is not necessarily surjective on isomorphisms. That is, if $f'$ is an isomorphism of $FG$ and $FH$, there does not necessarily exist any morphism $f:G\to H$ such that $Ff=f'$. However, if there does, it must be an isomorphism (since $F$ reflects isomorphisms).

NOTE: The above proof still feels a little suspicious to me, and there may be some holes that I'm missing...

MacLane has an interesting way of defining graphs categorically. He says that a directed graph $G$ consists of a set $O$ of objects/vertices and a set $A$ of arrows/edges, and a pair of functions $\partial_0,\partial_1:A\rightrightarrows O$ where $\partial_0$ gets the initial vertex/domain of each $f\in A$, and $\partial_1$ gets the terminal vertex/codomain of each $f\in A$. A morphism of graphs, or a digraph homomorphism, consists of a pair of functions $D_O:O\to O'$ and $D_A:A\to A'$ such that It is straightforward to see that this is equivalent to the usual definition of a graph homomorphism for (not necessarily simple) digraphs. This definition, although somewhat obscure, is illuminating because it reveals that the category $\mathsf{Dgr}$ is equivalent to the functor category $\mathsf{Set}^{\rightrightarrows}$, where $\rightrightarrows$ represents the category $\cdot\rightrightarrows\cdot$ with two objects.