Franklin's Notes


Categories of graphs

The following are commonly used categories whose objects are graphs:

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:

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:

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

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.

category-theory

graph-theory

back to home page