Pushouts in the category of graphs with Serre's definition.

Question

I am following Stallings 'Topology of Finite Graphs' were graphs are formulated according to Serre; that is, a graph consists of two sets $E$ and $V$ and two functions $E\rightarrow E$ and E$\rightarrow$ V: For each $e\in E$, there is an element $\bar{e}\in E$, and an element $\iota(e)\in E$. The rules to be satisfied are just these: $\bar{\bar{e}}= e$ and $\bar{e}\neq e$.
According to the notes, pushouts do not always exist in the category of graphs. However, I have been finding a counter example and I have only found this one: Pullbacks and pushouts in the category of graphs, but it does not seem to satisfy my counter example because I think that a graph with a unique vertex and a unique edge can be a candidate for the object of the pushout.
Can anyone help me, please? The notes of Stallings are these ones: https://pdfs.semanticscholar.org/6454/72563d649d6d20d4bd5b8a980b684155aa9d.pdf

Answer 1

The paper contains the following paragraph

In graphs, pushouts do not always exist. The reason is that a pushout of free $\mathbb Z/2$-sets may not be free. The necessary and sufficient condition for the pushout of a pair of maps of graphs, $\alpha_1\colon \Gamma\to\Delta_1$ and $\alpha_2\colon\Gamma\to\Delta_2$, to exist is that there exist orientations of $\Gamma,\Delta_1,\Delta_2$ which are preserved by $\alpha_1$ and $\alpha_2$. When this condition is satisfied, the pushout is "obvious."

The relevance of free (non-empty!) $\mathbb Z/2$-sets is that the subcategory of graphs with a single vertex is precisely the category of free $\mathbb Z/2$ sets. Furthermore, the subcategory has the property that any cocone on a connected diagram valued in the subcategory factors through a cocone with vertex in the subcategory (simply take the "image" graph of all the morphisms of the cocone -- it has to have a single vertex). In other words, any colimit of a connected diagram of graphs with one vertex will be itself be a graph with one vertex, if it exists.

Since the empty graph fulfills Serre's definition, we can apply the following general strategy to determining is pushouts exist. First check that coproducts exist (they do: take disjoint unions of graphs). Since they exist, the existence of pushouts becomes, using basic category theory, equivalent to the existence of coequalizers (also: if coproducts did not exist we would be done since the presence of the empty graph implies coproducts are themselves pushouts). We are now reduced to checking the existence of coequalizers in the category of graphs.

Then it is straightforward to check that a necessary condition for a pair of morphisms $\Gamma_1\overset{f_1}{\underset{f_2}{\rightrightarrows}}\Gamma_2$ to even have a cococone is that for every pair $\{e,\bar e\}$ of edges in $\Gamma_2$, it is not the case that both $f_1^{-1}(e)\cap f_2^{-1}(e)$ and $f_1^{-1}(e)\cap f_2^{-1}(\bar e)$ are non-trivial. In other words, picking an orienation on $\{e,\bar e\}$ induces compatible orientations on $f_1^{-1}(e)$ and $f_2^{-2}(e)$. In particular, for any graph $G$ with non-empty set of vertices $E$ the pair of the identity and "orientation-reversing" morphisms $G\underset{\mathrm{id}}{\overset{\bar\cdot}\rightrightarrows} G$ does not have cocones so lacks a coequalizer.

It turns out that the orientation condition, which guarantees the existence of cocones, is is also sufficient for the existence of universal cocones, i.e. coequalizers. Unraveling it in terms of pushouts should give the orientation condition for pushouts from the above paragraph.

Answer 2

Having a unique edge is not possible since if $e$ is that edge, $\overline e = e$ since that's the only option. What I think you mean is that you can have an edge pair, in fact many, between a single vertex. In particular, consider $E = \{(1,2),(2,1)\}$ with $\overline{(x,y)} = (y,x)$ and $\iota(e) = 3$ and $V = \{3\}$. This is a graph with one edge pair going from $3$ to $3$. But we can consider the coequalizer of $$(\overline{(\cdot)},id) : (E, V) \to (E, V)$$ with $id$ using the same $E$ and $V$ as before. It's easy to check that the above arrow is a homomorphism. Ultimately, though, $E$ and $V$ are just sets, and, in fact, ignoring the $\overline e \neq e$ condition, these graphs are presheaves. Thus, colimits are computed pointwise. Ignoring the $\overline e \neq e$ condition, the colimits always exist, but they need not satisfy that condition even if the input to the colimit does. Since $E$ always has even cardinality when finite, anything that leads to an odd cardinality is illegal. At any rate, it's easy to calculate the above coequalizer which simply identifies $(1,2)$ with $(2,1)$. The result is the pair of sets $(\{\{(1,2),(2,1)\}\},\{3\})$ which has only one element in its edge set, and so does not satisfy the $\overline e \neq e$ constraint.

To get a pushout, simply use the general result that coequalizers can be calculated from pushouts and coproducts. (It's easy to see that coproducts do exist.)