\documentclass[12pt,titlepage]{article} \usepackage{amsmath} \usepackage{mathrsfs} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsthm} \usepackage{mathtools} \usepackage{graphicx} \usepackage{color} \usepackage{ucs} \usepackage[utf8x]{inputenc} \usepackage{xparse} \usepackage{hyperref} %----Macros---------- % % Unresolved issues: % % \righttoleftarrow % \lefttorightarrow % % \color{} with HTML colorspec % \bgcolor % \array with options (without options, it's equivalent to the matrix environment) % Of the standard HTML named colors, white, black, red, green, blue and yellow % are predefined in the color package. Here are the rest. \definecolor{aqua}{rgb}{0, 1.0, 1.0} \definecolor{fuschia}{rgb}{1.0, 0, 1.0} \definecolor{gray}{rgb}{0.502, 0.502, 0.502} \definecolor{lime}{rgb}{0, 1.0, 0} \definecolor{maroon}{rgb}{0.502, 0, 0} \definecolor{navy}{rgb}{0, 0, 0.502} \definecolor{olive}{rgb}{0.502, 0.502, 0} \definecolor{purple}{rgb}{0.502, 0, 0.502} \definecolor{silver}{rgb}{0.753, 0.753, 0.753} \definecolor{teal}{rgb}{0, 0.502, 0.502} % Because of conflicts, \space and \mathop are converted to % \itexspace and \operatorname during preprocessing. % itex: \space{ht}{dp}{wd} % % Height and baseline depth measurements are in units of tenths of an ex while % the width is measured in tenths of an em. \makeatletter \newdimen\itex@wd% \newdimen\itex@dp% \newdimen\itex@thd% \def\itexspace#1#2#3{\itex@wd=#3em% \itex@wd=0.1\itex@wd% \itex@dp=#2ex% \itex@dp=0.1\itex@dp% \itex@thd=#1ex% \itex@thd=0.1\itex@thd% \advance\itex@thd\the\itex@dp% \makebox[\the\itex@wd]{\rule[-\the\itex@dp]{0cm}{\the\itex@thd}}} \makeatother % \tensor and \multiscript \makeatletter \newif\if@sup \newtoks\@sups \def\append@sup#1{\edef\act{\noexpand\@sups={\the\@sups #1}}\act}% \def\reset@sup{\@supfalse\@sups={}}% \def\mk@scripts#1#2{\if #2/ \if@sup ^{\the\@sups}\fi \else% \ifx #1_ \if@sup ^{\the\@sups}\reset@sup \fi {}_{#2}% \else \append@sup#2 \@suptrue \fi% \expandafter\mk@scripts\fi} \def\tensor#1#2{\reset@sup#1\mk@scripts#2_/} \def\multiscripts#1#2#3{\reset@sup{}\mk@scripts#1_/#2% \reset@sup\mk@scripts#3_/} \makeatother % \slash \makeatletter \newbox\slashbox \setbox\slashbox=\hbox{$/$} \def\itex@pslash#1{\setbox\@tempboxa=\hbox{$#1$} \@tempdima=0.5\wd\slashbox \advance\@tempdima 0.5\wd\@tempboxa \copy\slashbox \kern-\@tempdima \box\@tempboxa} \def\slash{\protect\itex@pslash} \makeatother % math-mode versions of \rlap, etc % from Alexander Perlis, "A complement to \smash, \llap, and lap" % http://math.arizona.edu/~aprl/publications/mathclap/ \def\clap#1{\hbox to 0pt{\hss#1\hss}} \def\mathllap{\mathpalette\mathllapinternal} \def\mathrlap{\mathpalette\mathrlapinternal} \def\mathclap{\mathpalette\mathclapinternal} \def\mathllapinternal#1#2{\llap{$\mathsurround=0pt#1{#2}$}} \def\mathrlapinternal#1#2{\rlap{$\mathsurround=0pt#1{#2}$}} \def\mathclapinternal#1#2{\clap{$\mathsurround=0pt#1{#2}$}} % Renames \sqrt as \oldsqrt and redefine root to result in \sqrt[#1]{#2} \let\oldroot\root \def\root#1#2{\oldroot #1 \of{#2}} \renewcommand{\sqrt}[2][]{\oldroot #1 \of{#2}} % Manually declare the txfonts symbolsC font \DeclareSymbolFont{symbolsC}{U}{txsyc}{m}{n} \SetSymbolFont{symbolsC}{bold}{U}{txsyc}{bx}{n} \DeclareFontSubstitution{U}{txsyc}{m}{n} % Manually declare the stmaryrd font \DeclareSymbolFont{stmry}{U}{stmry}{m}{n} \SetSymbolFont{stmry}{bold}{U}{stmry}{b}{n} % Manually declare the MnSymbolE font \DeclareFontFamily{OMX}{MnSymbolE}{} \DeclareSymbolFont{mnomx}{OMX}{MnSymbolE}{m}{n} \SetSymbolFont{mnomx}{bold}{OMX}{MnSymbolE}{b}{n} \DeclareFontShape{OMX}{MnSymbolE}{m}{n}{ <-6> MnSymbolE5 <6-7> MnSymbolE6 <7-8> MnSymbolE7 <8-9> MnSymbolE8 <9-10> MnSymbolE9 <10-12> MnSymbolE10 <12-> MnSymbolE12}{} % Declare specific arrows from txfonts without loading the full package \makeatletter \def\re@DeclareMathSymbol#1#2#3#4{% \let#1=\undefined \DeclareMathSymbol{#1}{#2}{#3}{#4}} \re@DeclareMathSymbol{\neArrow}{\mathrel}{symbolsC}{116} \re@DeclareMathSymbol{\neArr}{\mathrel}{symbolsC}{116} \re@DeclareMathSymbol{\seArrow}{\mathrel}{symbolsC}{117} \re@DeclareMathSymbol{\seArr}{\mathrel}{symbolsC}{117} \re@DeclareMathSymbol{\nwArrow}{\mathrel}{symbolsC}{118} \re@DeclareMathSymbol{\nwArr}{\mathrel}{symbolsC}{118} \re@DeclareMathSymbol{\swArrow}{\mathrel}{symbolsC}{119} \re@DeclareMathSymbol{\swArr}{\mathrel}{symbolsC}{119} \re@DeclareMathSymbol{\nequiv}{\mathrel}{symbolsC}{46} \re@DeclareMathSymbol{\Perp}{\mathrel}{symbolsC}{121} \re@DeclareMathSymbol{\Vbar}{\mathrel}{symbolsC}{121} \re@DeclareMathSymbol{\sslash}{\mathrel}{stmry}{12} \re@DeclareMathSymbol{\bigsqcap}{\mathop}{stmry}{"64} \re@DeclareMathSymbol{\biginterleave}{\mathop}{stmry}{"6} \re@DeclareMathSymbol{\invamp}{\mathrel}{symbolsC}{77} \re@DeclareMathSymbol{\parr}{\mathrel}{symbolsC}{77} \makeatother % \llangle, \rrangle, \lmoustache and \rmoustache from MnSymbolE \makeatletter \def\Decl@Mn@Delim#1#2#3#4{% \if\relax\noexpand#1% \let#1\undefined \fi \DeclareMathDelimiter{#1}{#2}{#3}{#4}{#3}{#4}} \def\Decl@Mn@Open#1#2#3{\Decl@Mn@Delim{#1}{\mathopen}{#2}{#3}} \def\Decl@Mn@Close#1#2#3{\Decl@Mn@Delim{#1}{\mathclose}{#2}{#3}} \Decl@Mn@Open{\llangle}{mnomx}{'164} \Decl@Mn@Close{\rrangle}{mnomx}{'171} \Decl@Mn@Open{\lmoustache}{mnomx}{'245} \Decl@Mn@Close{\rmoustache}{mnomx}{'244} \makeatother % Widecheck \makeatletter \DeclareRobustCommand\widecheck[1]{{\mathpalette\@widecheck{#1}}} \def\@widecheck#1#2{% \setbox\z@\hbox{\m@th$#1#2$}% \setbox\tw@\hbox{\m@th$#1% \widehat{% \vrule\@width\z@\@height\ht\z@ \vrule\@height\z@\@width\wd\z@}$}% \dp\tw@-\ht\z@ \@tempdima\ht\z@ \advance\@tempdima2\ht\tw@ \divide\@tempdima\thr@@ \setbox\tw@\hbox{% \raise\@tempdima\hbox{\scalebox{1}[-1]{\lower\@tempdima\box \tw@}}}% {\ooalign{\box\tw@ \cr \box\z@}}} \makeatother % \mathraisebox{voffset}[height][depth]{something} \makeatletter \NewDocumentCommand\mathraisebox{moom}{% \IfNoValueTF{#2}{\def\@temp##1##2{\raisebox{#1}{$\m@th##1##2$}}}{% \IfNoValueTF{#3}{\def\@temp##1##2{\raisebox{#1}[#2]{$\m@th##1##2$}}% }{\def\@temp##1##2{\raisebox{#1}[#2][#3]{$\m@th##1##2$}}}}% \mathpalette\@temp{#4}} \makeatletter % udots (taken from yhmath) \makeatletter \def\udots{\mathinner{\mkern2mu\raise\p@\hbox{.} \mkern2mu\raise4\p@\hbox{.}\mkern1mu \raise7\p@\vbox{\kern7\p@\hbox{.}}\mkern1mu}} \makeatother %% Fix array \newcommand{\itexarray}[1]{\begin{matrix}#1\end{matrix}} %% \itexnum is a noop \newcommand{\itexnum}[1]{#1} %% Renaming existing commands \newcommand{\underoverset}[3]{\underset{#1}{\overset{#2}{#3}}} \newcommand{\widevec}{\overrightarrow} \newcommand{\darr}{\downarrow} \newcommand{\nearr}{\nearrow} \newcommand{\nwarr}{\nwarrow} \newcommand{\searr}{\searrow} \newcommand{\swarr}{\swarrow} \newcommand{\curvearrowbotright}{\curvearrowright} \newcommand{\uparr}{\uparrow} \newcommand{\downuparrow}{\updownarrow} \newcommand{\duparr}{\updownarrow} \newcommand{\updarr}{\updownarrow} \newcommand{\gt}{>} \newcommand{\lt}{<} \newcommand{\map}{\mapsto} \newcommand{\embedsin}{\hookrightarrow} \newcommand{\Alpha}{A} \newcommand{\Beta}{B} \newcommand{\Zeta}{Z} \newcommand{\Eta}{H} \newcommand{\Iota}{I} \newcommand{\Kappa}{K} \newcommand{\Mu}{M} \newcommand{\Nu}{N} \newcommand{\Rho}{P} \newcommand{\Tau}{T} \newcommand{\Upsi}{\Upsilon} \newcommand{\omicron}{o} \newcommand{\lang}{\langle} \newcommand{\rang}{\rangle} \newcommand{\Union}{\bigcup} \newcommand{\Intersection}{\bigcap} \newcommand{\Oplus}{\bigoplus} \newcommand{\Otimes}{\bigotimes} \newcommand{\Wedge}{\bigwedge} \newcommand{\Vee}{\bigvee} \newcommand{\coproduct}{\coprod} \newcommand{\product}{\prod} \newcommand{\closure}{\overline} \newcommand{\integral}{\int} \newcommand{\doubleintegral}{\iint} \newcommand{\tripleintegral}{\iiint} \newcommand{\quadrupleintegral}{\iiiint} \newcommand{\conint}{\oint} \newcommand{\contourintegral}{\oint} \newcommand{\infinity}{\infty} \newcommand{\bottom}{\bot} \newcommand{\minusb}{\boxminus} \newcommand{\plusb}{\boxplus} \newcommand{\timesb}{\boxtimes} \newcommand{\intersection}{\cap} \newcommand{\union}{\cup} \newcommand{\Del}{\nabla} \newcommand{\odash}{\circleddash} \newcommand{\negspace}{\!} \newcommand{\widebar}{\overline} \newcommand{\textsize}{\normalsize} \renewcommand{\scriptsize}{\scriptstyle} \newcommand{\scriptscriptsize}{\scriptscriptstyle} \newcommand{\mathfr}{\mathfrak} \newcommand{\statusline}[2]{#2} \newcommand{\tooltip}[2]{#2} \newcommand{\toggle}[2]{#2} % Theorem Environments \theoremstyle{plain} \newtheorem{theorem}{Theorem} \newtheorem{lemma}{Lemma} \newtheorem{prop}{Proposition} \newtheorem{cor}{Corollary} \newtheorem*{utheorem}{Theorem} \newtheorem*{ulemma}{Lemma} \newtheorem*{uprop}{Proposition} \newtheorem*{ucor}{Corollary} \theoremstyle{definition} \newtheorem{defn}{Definition} \newtheorem{example}{Example} \newtheorem*{udefn}{Definition} \newtheorem*{uexample}{Example} \theoremstyle{remark} \newtheorem{remark}{Remark} \newtheorem{note}{Note} \newtheorem*{uremark}{Remark} \newtheorem*{unote}{Note} %------------------------------------------------------------------- \begin{document} %------------------------------------------------------------------- \section*{category of simple graphs} \hypertarget{context}{}\subsubsection*{{Context}}\label{context} \hypertarget{graph_theory}{}\paragraph*{{Graph theory}}\label{graph_theory} [[!include graph theory - contents]] \hypertarget{category_theory}{}\paragraph*{{Category theory}}\label{category_theory} [[!include category theory - contents]] \hypertarget{contents}{}\section*{{Contents}}\label{contents} \noindent\hyperlink{introduction}{Introduction}\dotfill \pageref*{introduction} \linebreak \noindent\hyperlink{simple_graphs_as_relations}{Simple graphs as relations}\dotfill \pageref*{simple_graphs_as_relations} \linebreak \noindent\hyperlink{an_aside_on_other_notions_of_graph}{An aside on other notions of graph}\dotfill \pageref*{an_aside_on_other_notions_of_graph} \linebreak \noindent\hyperlink{properties_of_}{Properties of $SimpGph$}\dotfill \pageref*{properties_of_} \linebreak \noindent\hyperlink{equalizers_and_coequalizers}{Equalizers and coequalizers}\dotfill \pageref*{equalizers_and_coequalizers} \linebreak \noindent\hyperlink{ternary_factorization}{Ternary factorization}\dotfill \pageref*{ternary_factorization} \linebreak \noindent\hyperlink{subcategories}{Subcategories}\dotfill \pageref*{subcategories} \linebreak \noindent\hyperlink{natural_numbers_object}{Natural numbers object}\dotfill \pageref*{natural_numbers_object} \linebreak \noindent\hyperlink{references}{References}\dotfill \pageref*{references} \linebreak \hypertarget{introduction}{}\subsection*{{Introduction}}\label{introduction} Both [[category theory]] and [[graph theory]] study patterns based on [[diagrams]] consisting of nodes and edges. Despite this surface impression, there is in fact very little interaction between the scientific communities of category theorists and of graph theorists. This article is a modest bridge, indicating that the \emph{[[category]] of [[graphs]]} (in the usual graph-theorist's sense -- see for example \hyperlink{Diestel}{Diestel}) has some very nice properties. \hypertarget{simple_graphs_as_relations}{}\subsection*{{Simple graphs as relations}}\label{simple_graphs_as_relations} By a \textbf{simple [[graph]]}, we mean a [[set]] $V$ whose elements are called \emph{vertices}, together with a collection of 2-element subsets $\{x, y\}$ of $V$; these are called \emph{edges} of the graph. There are various ways of forming a category of simple graphs. Perhaps the most straightforward is to define a graph morphism $G \to H$ to be a function $f: V \to W$ between the vertex sets such that $\{f(x), f(y)\}$ is an edge of $H$ whenever $\{x, y\}$ is an edge of $G$. Another option -- and this is the one chosen for this article -- starts by regarding a simple graph as carrying the same information as a set $V$ equipped with a [[symmetric relation|symmetric]] [[reflexive relation|reflexive]] [[relation]] $E$. Indeed, such a relation determines (and is uniquely determined by) a simple graph $G$ where for given vertices $x, y \in V$, there is an edge $\{x, y\}$ between $x$ and $y$ in $G$ iff both $(x, y) \in E$ and $x \neq y$. We will write $E(x, y)$ to mean $(x, y) \in E$. Then, under the relational formulation, we define a morphism $(V, E) \to (W, F)$ between simple graphs straightforwardly\footnote{In other words, the usual notion of morphism between structures or models as in [[model theory]].} as a function $f: V \to W$ that preserves the relevant structure, i.e., that $E(x, y)$ implies $F(f(x), f(y))$. One reason for preferring this notion of morphism is that it allows, for example, consideration of arbitrary edge contractions of a simple graph as [[quotients]] in the category (cf. [[graph minor]]), something that is not possible under the prior notion of morphism. Thus we will adopt the latter notion of morphism which takes reflexive symmetric relations $E$ as primary. The resulting [[category]] of simple graphs is denoted by $SimpGph$. Note that graphs and their morphisms can also be understood in functorial language, by regarding simple graphs as special types of [[presheaves]], as follows. Let $C$ be the category of sets $1 \coloneqq \{\ast\}$ and $2 \coloneqq \{s, t\}$ and functions between them. Then a presheaf $X: C^{op} \to Set$ is given by sets $V = X(1)$ and $E = X(2)$ and maps \begin{itemize}% \item $d_0: X(2) \stackrel{X(\ast \mapsto s)}{\to} X(1)$ (source map), \item $d_1: X(2) \stackrel{X(\ast \mapsto t)}{\to} X(1)$ (target map), \item $i: X(1) \stackrel{X(s, t \mapsto \ast)}{\to} X(2)$ (reflexive map), \item $\sigma: X(2) \stackrel{X(s \mapsto t, t \mapsto s)}{\to} X(2)$ (symmetry map). \end{itemize} satisfying appropriate identities imposed by equations in $C$. Simple graphs can then be regarded [[equivalence|equivalently]] as such presheaves where the map \begin{displaymath} \langle d_0, d_1 \rangle: X(2) \to X(1) \times X(1) \end{displaymath} is a [[monomorphism]]. In that case, a morphism of simple graphs amounts to a [[natural transformation]] between such presheaves. \hypertarget{an_aside_on_other_notions_of_graph}{}\subsubsection*{{An aside on other notions of graph}}\label{an_aside_on_other_notions_of_graph} ``Simple graph'' as defined in the nLab (see [[graph]]) means that edges are 2-element subsets of $V$, but of course that doesn't preclude consideration of other types of graph. One option is to consider sets $V$ equipped with a collection of subsets of $V$ of cardinality either 1 or 2, i.e., allowing some but not necessarily all loops as edges. We don't call those ``simple graphs'' (at [[graph]] they are called ``loop graphs''), but nevertheless they form a respectable category under the straightforward notion of morphism $f$ (if $\{x, y\}$ is an edge of the domain, possibly with $x = y$, then $\{f(x), f(y)\}$ is an edge of the codomain). Chih and Scull use this category, which they refer to as $Gph$, in their paper \hyperlink{ChihScul}{\emph{Homotopy in the Category of Graphs}}. \hypertarget{properties_of_}{}\subsection*{{Properties of $SimpGph$}}\label{properties_of_} The category $SimpGph$ has very good properties. For example, \begin{theorem} \label{}\hypertarget{}{} $SimpGph$ is a [[Grothendieck quasitopos]]. In particular, it is a [[regular category]] and even a [[logos]], and $SimpGph^{op}$ is also regular. It is also $\infty$-[[extensive category|extensive]]. \end{theorem} \begin{proof} (See also \hyperlink{AdamHerr}{Adamek and Herrlich}.) As above, let $C$ be the category of sets $1$ and $2$ and functions between them, and regard the category of simple graphs as a full subcategory of the presheaf [[topos]] $Set^{C^{op}}$. For this presheaf topos, there is just one nontrivial $\neg\neg$-dense sieve, namely the inclusion \begin{displaymath} (s, t): C(-, 1) + C(-, 1) \to C(-, 2) \end{displaymath} (where $s$ is shorthand for $C(-, \ast \mapsto s)$ and similarly for $t$) and so the category of $\neg\neg$-[[separated presheaves]] is equivalent to the category of presheaves $X$ such that the induced map \begin{displaymath} X(2) \cong Set^{C^{op}}(C(-, 2), X) \stackrel{(s, t)^\ast}{\to} Set^{C^{op}}(C(-, 1) + C(-, 1), X) \cong X(1) \times X(1), \end{displaymath} which is the source-target pairing $\langle d_0, d_1 \rangle: X(2) \to X(1) \times X(1)$, is monic. In other words, a simple graph in this language is exactly a separated presheaf. On the other hand, a Grothendieck quasitopos is, essentially by definition, the category of separated presheaves for a topology on a presheaf topos, in this case the $\neg\neg$-topology. Being a quasitopos with small coproducts, it is $\infty$-extensive provided that coproducts are disjoint. However, this is trivial to check (it even suffices to check, according to [[Elephant]] 2.6.5, that $0 \to 1$ is a [[regular monomorphism]], or that $1 + 1$ is a disjoint coproduct, which it obviously is). \end{proof} \begin{remark} \label{quasitopos}\hypertarget{quasitopos}{} Implicit in this proof is the way in which (for example) limits of simple graphs are calculated. Since $SimpGph$ is realized as a category of separated presheaves which is a [[reflective subcategory]] of all presheaves, limits in $SimpGph$ are calculated just as they are in the presheaf category $Set^{C^{op}}$, which is to say: they are computed objectwise, at the objects $1, 2$ of $C$. For example, consider how to construct the [[equalizer]] of a pair of graph maps $f, g: G \rightrightarrows H$. For the vertex set of the equalizer (computing the equalizer at the object $1$ of $C$), one just takes the equalizer of the functions between the vertex sets of $G$ and $H$. At the edge set level where we have maps $E = G(2) \rightrightarrows F = H(2)$: since there is at most one edge between two vertices, the maps $f(2), g(2)$ must agree on $e \in E$ provided $f(d_0 e) = g(d_0 e)$ and $f(d_1 e) = g(d_1 e)$, so the equalizer graph is just the full or [[graph|induced subgraph]] of $G$ given by the equalizer vertex set. Moreover, every induced subgraph $H \hookrightarrow G$ arises as an equalizer (consider the equalizer of the two embeddings of $G$ into the amalgamation $G +_H G$, which at the vertex level agrees with $H \hookrightarrow G$). Of course this is elementary, but we get much more more: the quasitopos $SimpGph$ is also a [[locally cartesian closed category]], and [[dependent products]] can also be read off directly from how they work for presheaves. \end{remark} It is easy to describe [[monomorphism|monos]] and [[epimorphism|epis]] in $SimpGph$. For, let $\Gamma = \hom(1, -): SimpGph \to Set$ be the underlying vertex-set [[forgetful functor]]. \begin{prop} \label{EmbeddingOfSimpGphIntoSet}\hypertarget{EmbeddingOfSimpGphIntoSet}{} The forgetful functor $\Gamma = \hom(1, -): SimpGph \to Set$ is faithful, in fact exhibits $SimpGph$ as a [[topological concrete category]]. \end{prop} We omit the easy proof. Next we have two easy results: \begin{prop} \label{}\hypertarget{}{} $\Gamma$ [[reflected limit|reflects]] monos and epis (because $\Gamma$ is faithful). \end{prop} \begin{prop} \label{}\hypertarget{}{} $\Gamma$ [[preserved limit|preserves]] [[limits]] and [[colimits]] (because it has a [[left adjoint]] $\Delta$ and a [[right adjoint]] $\nabla$). \end{prop} It follows that $\Gamma: SimpGph \to Set$ both preserves and reflects monos and epis. As a result, we can prove various simple exactness results in $SimpGph$. For instance: \begin{lemma} \label{}\hypertarget{}{} In $SimpGph$, the [[pushout]] of any mono is a mono. \end{lemma} \begin{proof} Suppose we have a pushout diagram in $SimpGph$: \begin{displaymath} \itexarray{ G & \to & H \\ ^\mathllap{mono} \downarrow & & \downarrow^\mathrlap{k} \\ G' & \to & H' } \end{displaymath} Since $\Gamma$ preserves both pushouts and monos, and since the pushout of a mono in $Set$ is a mono, we have that $\Gamma(k)$ is monic in $Set$. Since $\Gamma$ reflects monos, this means $k$ is monic in $SimpGph$. \end{proof} As already observed, there is a chain of adjoint functors $\Delta \dashv \Gamma \dashv \nabla: Set \to SimpGph$. But in fact there is a fourth functor in the chain: $\Delta$ has a left adjoint $\Pi: SimpGph \to Set$, the [[connected object|connected components]] functor. If $E$ is the simple graph consisting of two vertices $a, b$ with an edge between them, then there is a reflexive fork \begin{displaymath} a, b: 1 \rightrightarrows E \stackrel{!}{\to} 1 \end{displaymath} and $\Pi$ is formed as a [[reflexive coequalizer]] of the induced diagram: \begin{displaymath} SimpGph(1, -) \to SimpGph(E, -) \rightrightarrows SimpGph(1, -) \to \Pi \end{displaymath} \begin{prop} \label{}\hypertarget{}{} $\Pi \dashv \Delta$, and $\Pi$ preserves products. \end{prop} \begin{proof} $\Pi$ preserves products because being a reflexive coequalizer, it is a [[sifted colimit]] of product-preserving functors. For graphs $G$, there is a natural map $u G: G \to \Delta \Pi G$ which at the underlying vertex-set level sends a vertex to its connected component; if $S$ is any set, then a graph map $f: G \to \Delta S$ must send any two vertices with an edge between them to the same point, and so $f$ factors as $G \stackrel{u G}{\to} \Delta \Pi G \stackrel{\Delta g}{\to} \Delta S$ for a unique map $g: \Pi G \to S$, and this establishes the adjunction $\Pi \dashv \Delta$. \end{proof} \hypertarget{equalizers_and_coequalizers}{}\subsubsection*{{Equalizers and coequalizers}}\label{equalizers_and_coequalizers} If $f, g \colon G \stackrel{\to}{\to} H$ are maps in $SimpGph$, then their [[equalizer]] $Eq(f, g) = i \colon K \to G$ is given at the vertex level by \begin{displaymath} \Gamma(i) = Eq(\Gamma(f), \Gamma(g)) \end{displaymath} and at the edge level by $K(x, y) \Leftrightarrow G(i(x), i(y))$; in other words, if $x, y$ belong to $K$ and there is an edge between them in $G$, then that edge lies in $K$. To express this last condition, we say the subgraph $i$ is \emph{full} (at the edge level). Thus, $i$ is a regular mono in $SimpGph$ iff both $\Gamma(i)$ is monic in $Set$ and $i$ is full at the edge level (see Remark \ref{quasitopos}). The [[coequalizer]] of $f$ and $g$, say $Coeq(f, g) = q \colon H \to Q$, is given at the vertex level by \begin{displaymath} \Gamma(q) = Coeq(\Gamma(f), \Gamma(g)) \end{displaymath} and at the edge level by taking the image of the composite $E_H \hookrightarrow Vert(H)^2 \stackrel{q^2}{\to} Vert(Q)^2$, so that \begin{displaymath} Q(x, y) \Leftrightarrow \exists_{u, v} H(u, v) \wedge q(u) = x \wedge q(v) = y. \end{displaymath} Thus, $q$ is a [[regular epimorphism]] if it is surjective at both the vertex and edge levels. \hypertarget{ternary_factorization}{}\subsubsection*{{Ternary factorization}}\label{ternary_factorization} The category of simple graphs has a [[ternary factorization system]] as follows: each morphism $f \colon G \to H$ factors as \begin{displaymath} G \stackrel{q}{\to} G' \stackrel{a}{\to} H' \stackrel{i}{\to} H \end{displaymath} where \begin{itemize}% \item $q$ is a surjection between vertex-sets and at the edge level, i.e., is a [[regular epi]]; \item $a$ induces an identity between vertex-sets (hence is [[bimorphism|jointly monic and epic]]), but without necessarily being full at the edge level; \item $i$ is given by an injection between vertex-sets and is full at the edge level, and (thus) is a [[regular mono]]. \end{itemize} The factorization of $f$ into $q$ followed by $i \circ a$ is the (regular epi)-mono factorization, while the factorization of $f$ into $a \circ q$ followed by $i$ is the epi-(regular mono) factorization. (The fact that regular monos are stable under pushout, used to ensure that the epi-(regular mono) factorization is an [[orthogonal factorization system]], is true because $SimpGph$, being a [[quasitopos]], is a \emph{coregular category}, meaning $SimpGph^{op}$ is [[regular category|regular]].) Both factorizations coincide at the level of underlying functions between vertex sets, both being the usual epi-mono factorization. In particular, we have the easy facts that \begin{itemize}% \item $f$ is a mono iff $q$ is a graph isomorphism: monos in $SimpGph$ are simple graph maps that are injective on vertices and edges, \item $f$ is an epi iff $i$ is a graph isomorphism: epis in $SimpGph$ are simple graph maps that are surjective on vertices. \end{itemize} \hypertarget{subcategories}{}\subsubsection*{{Subcategories}}\label{subcategories} Graph theory suggests both full and wide subcategories of $SimpGph$. See [[the category of simple graphs from a graph-theoretic perspective]] for more details. \hypertarget{natural_numbers_object}{}\subsubsection*{{Natural numbers object}}\label{natural_numbers_object} The category $SimpGph$ has a [[natural numbers object]]; on abstract grounds this is formed by applying the reflection functor \begin{displaymath} L: Set^{C^{op}} \to SimpGph \end{displaymath} to the natural numbers object in $Set^{C^{op}}$. \hypertarget{references}{}\subsection*{{References}}\label{references} \begin{itemize}% \item [[Jiří Adámek]] and Horst Herrlich, \emph{Cartesian closed categories, quasitopoi, and topological universes}. Comm. Math. Univ. Carol., Vol. 27, No. 2 (1986), 235-257. (\href{http://dml.cz/handle/10338.dmlcz/106447}{web}) \end{itemize} \begin{itemize}% \item [[Tien Chih]], [[Laura Scull]], \emph{Homotopy in the Category of Graphs}, (\href{https://arxiv.org/abs/1901.01619}{arXiv:1901.01619}) \end{itemize} \begin{itemize}% \item Reinhard Diestel, Graph Theory (Second Edition), Graduate Texts in Mathematics 173, Springer (2000). \end{itemize} category: category [[!redirects category of simple graphs]] [[!redirects Simp Gph]] [[!redirects SimpGph]] [[!redirects simple graph]] [[!redirects simple graphs]] \end{document}