CINXE.COM

<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.1 plus MathML 2.0 plus SVG 1.1//EN" "http://www.w3.org/2002/04/xhtml-math-svg/xhtml-math-svg-flat.dtd" > <html xmlns="http://www.w3.org/1999/xhtml"> <head> <title> graph in nLab </title> <meta http-equiv="Content-Type" content="text/html; charset=UTF-8" /> <meta name="robots" content="index,follow" /> <meta name="viewport" content="width=device-width, initial-scale=1" /> <link href="/stylesheets/instiki.css?1676280126" media="all" rel="stylesheet" type="text/css" /> <link href="/stylesheets/mathematics.css?1660229990" media="all" rel="stylesheet" type="text/css" /> <link href="/stylesheets/syntax.css?1660229990" media="all" rel="stylesheet" type="text/css" /> <link href="/stylesheets/nlab.css?1676280126" media="all" rel="stylesheet" type="text/css" /> <link rel="stylesheet" type="text/css" href="https://cdn.jsdelivr.net/gh/dreampulse/computer-modern-web-font@master/fonts.css"/> <style type="text/css"> h1#pageName, div.info, .newWikiWord a, a.existingWikiWord, .newWikiWord a:hover, [actiontype="toggle"]:hover, #TextileHelp h3 { color: #226622; } a:visited.existingWikiWord { color: #164416; } </style> <style type="text/css"><![CDATA[/*></style> <script src="/javascripts/prototype.js?1660229990" type="text/javascript"></script> <script src="/javascripts/effects.js?1660229990" type="text/javascript"></script> <script src="/javascripts/dragdrop.js?1660229990" type="text/javascript"></script> <script src="/javascripts/controls.js?1660229990" type="text/javascript"></script> <script src="/javascripts/application.js?1660229990" type="text/javascript"></script> <script src="/javascripts/page_helper.js?1660229990" type="text/javascript"></script> <script src="/javascripts/thm_numbering.js?1660229990" type="text/javascript"></script> <script type="text/x-mathjax-config"> <![CDATA[//><!]]> </script> <script type="text/javascript"> <![CDATA[//><!]]> </script> <link href="https://ncatlab.org/nlab/atom_with_headlines" rel="alternate" title="Atom with headlines" type="application/atom+xml" /> <link href="https://ncatlab.org/nlab/atom_with_content" rel="alternate" title="Atom with full content" type="application/atom+xml" /> <script type="text/javascript"> document.observe("dom:loaded", function() { generateThmNumbers(); }); </script> </head> <body> <div id="Container"> <div id="Content"> <h1 id="pageName"> <span style="float: left; margin: 0.5em 0.25em -0.25em 0"> <svg xmlns="http://www.w3.org/2000/svg" width="1.872em" height="1.8em" viewBox="0 0 190 181"> <path fill="#226622" d="M72.8 145c-1.6 17.3-15.7 10-23.6 20.2-5.6 7.3 4.8 15 11.4 15 11.5-.2 19-13.4 26.4-20.3 3.3-3 8.2-4 11.2-7.2a14 14 0 0 0 2.9-11.1c-1.4-9.6-12.4-18.6-16.9-27.2-5-9.6-10.7-27.4-24.1-27.7-17.4-.3-.4 26 4.7 30.7 2.4 2.3 5.4 4.1 7.3 6.9 1.6 2.3 2.1 5.8-1 7.2-5.9 2.6-12.4-6.3-15.5-10-8.8-10.6-15.5-23-26.2-31.8-5.2-4.3-11.8-8-18-3.7-7.3 4.9-4.2 12.9.2 18.5a81 81 0 0 0 30.7 23c3.3 1.5 12.8 5.6 10 10.7-2.5 5.2-11.7 3-15.6 1.1-8.4-3.8-24.3-21.3-34.4-13.7-3.5 2.6-2.3 7.6-1.2 11.1 2.8 9 12.2 17.2 20.9 20.5 17.3 6.7 34.3-8 50.8-12.1z"/> <path fill="#a41e32" d="M145.9 121.3c-.2-7.5 0-19.6-4.5-26-5.4-7.5-12.9-1-14.1 5.8-1.4 7.8 2.7 14.1 4.8 21.3 3.4 12 5.8 29-.8 40.1-3.6-6.7-5.2-13-7-20.4-2.1-8.2-12.8-13.2-15.1-1.9-2 9.7 9 21.2 12 30.1 1.2 4 2 8.8 6.4 10.3 6.9 2.3 13.3-4.7 17.7-8.8 12.2-11.5 36.6-20.7 43.4-36.4 6.7-15.7-13.7-14-21.3-7.2-9.1 8-11.9 20.5-23.6 25.1 7.5-23.7 31.8-37.6 38.4-61.4 2-7.3-.8-29.6-13-19.8-14.5 11.6-6.6 37.6-23.3 49.2z"/> <path fill="#193c78" d="M86.3 47.5c0-13-10.2-27.6-5.8-40.4 2.8-8.4 14.1-10.1 17-1 3.8 11.6-.3 26.3-1.8 38 11.7-.7 10.5-16 14.8-24.3 2.1-4.2 5.7-9.1 11-6.7 6 2.7 7.4 9.2 6.6 15.1-2.2 14-12.2 18.8-22.4 27-3.4 2.7-8 6.6-5.9 11.6 2 4.4 7 4.5 10.7 2.8 7.4-3.3 13.4-16.5 21.7-16 14.6.7 12 21.9.9 26.2-5 1.9-10.2 2.3-15.2 3.9-5.8 1.8-9.4 8.7-15.7 8.9-6.1.1-9-6.9-14.3-9-14.4-6-33.3-2-44.7-14.7-3.7-4.2-9.6-12-4.9-17.4 9.3-10.7 28 7.2 35.7 12 2 1.1 11 6.9 11.4 1.1.4-5.2-10-8.2-13.5-10-11.1-5.2-30-15.3-35-27.3-2.5-6 2.8-13.8 9.4-13.6 6.9.2 13.4 7 17.5 12C70.9 34 75 43.8 86.3 47.4z"/> </svg> </span> <span class="webName">nLab</span> graph </h1> <div class="navigation"> <span class="skipNav"><a href='#navEnd'>Skip the Navigation Links</a> | </span> <span style="display:inline-block; width: 0.3em;"></span> <a href="/nlab/show/HomePage" accesskey="H" title="Home page">Home Page</a> | <a href="/nlab/all_pages" accesskey="A" title="List of all pages">All Pages</a> | <a href="/nlab/latest_revisions" accesskey="U" title="Latest edits and page creations">Latest Revisions</a> | <a href="https://nforum.ncatlab.org/discussion/3726/#Item_24" title="Discuss this page in its dedicated thread on the nForum" style="color: black">Discuss this page</a> | <form accept-charset="utf-8" action="/nlab/search" id="navigationSearchForm" method="get"> <fieldset class="search"><input type="text" id="searchField" name="query" value="Search" style="display:inline-block; float: left;" onfocus="this.value == 'Search' ? this.value = '' : true" onblur="this.value == '' ? this.value = 'Search' : true" /></fieldset> </form> <span id='navEnd'></span> </div> <div id="revision"> <html xmlns="http://www.w3.org/1999/xhtml" xmlns:svg="http://www.w3.org/2000/svg" xml:lang="en" lang="en"> <head><meta http-equiv="Content-type" content="application/xhtml+xml;charset=utf-8" /><title>Contents</title></head> <body> <blockquote> <p>This page is about the notion in <a class="existingWikiWord" href="/nlab/show/combinatorics">combinatorics</a>. For other notions of the same name see at <em><a class="existingWikiWord" href="/nlab/show/graph+of+a+function">graph of a function</a></em> and <em><a class="existingWikiWord" href="/nlab/show/graph+of+a+functor">graph of a functor</a></em>.</p> </blockquote> <hr /> <div class="rightHandSide"> <div class="toc clickDown" tabindex="0"> <h3 id="context">Context</h3> <h4 id="graph_theory">Graph theory</h4> <div class="hide"><div> <p><strong><a class="existingWikiWord" href="/nlab/show/graph+theory">graph theory</a></strong></p> <p><a class="existingWikiWord" href="/nlab/show/graph">graph</a></p> <ul> <li> <p><a class="existingWikiWord" href="/nlab/show/vertex">vertex</a>, <a class="existingWikiWord" href="/nlab/show/edge">edge</a></p> </li> <li> <p><a class="existingWikiWord" href="/nlab/show/omega-graph">omega-graph</a>, <a class="existingWikiWord" href="/nlab/show/hypergraph">hypergraph</a></p> </li> <li> <p><a class="existingWikiWord" href="/nlab/show/quiver">quiver</a>, <a class="existingWikiWord" href="/nlab/show/n-quiver">n-quiver</a></p> </li> </ul> <p><a class="existingWikiWord" href="/nlab/show/category+of+simple+graphs">category of simple graphs</a></p> <h3 id="properties">Properties</h3> <ul> <li><a class="existingWikiWord" href="/nlab/show/graph+distance">graph distance</a></li> </ul> <h3 id="extra_properties">Extra properties</h3> <ul> <li> <p><a class="existingWikiWord" href="/nlab/show/reflexive+graph">reflexive</a>, <a class="existingWikiWord" href="/nlab/show/directed+graph">directed</a></p> </li> <li> <p><a class="existingWikiWord" href="/nlab/show/bipartite+graph">bipartite</a></p> </li> <li> <p><a class="existingWikiWord" href="/nlab/show/planar+graph">planar</a></p> </li> </ul> <h3 id="extra_structure">Extra structure</h3> <ul> <li> <p><a class="existingWikiWord" href="/nlab/show/reflexive+graph">reflexive</a><a class="existingWikiWord" href="/nlab/show/directed+graph">directed graph</a> + <a class="existingWikiWord" href="/nlab/show/unit+law">unital</a> <a class="existingWikiWord" href="/nlab/show/associative">associative</a> <a class="existingWikiWord" href="/nlab/show/composition">composition</a> = <a class="existingWikiWord" href="/nlab/show/category">category</a></p> </li> <li> <p><a class="existingWikiWord" href="/nlab/show/ribbon+graph">ribbon graph</a>, <a class="existingWikiWord" href="/nlab/show/combinatorial+map">combinatorial map</a>, <a class="existingWikiWord" href="/nlab/show/topological+map">topological map</a>, <a class="existingWikiWord" href="/nlab/show/child%27s+drawing">child's drawing</a></p> </li> <li> <p><a class="existingWikiWord" href="/nlab/show/vertex+coloring">vertex coloring</a>, <a class="existingWikiWord" href="/nlab/show/clique">clique</a></p> </li> </ul> </div></div> </div> </div> <h1 id="contents">Contents</h1> <div class='maruku_toc'> <ul> <li><a href='#idea'>Idea</a></li> <li><a href='#definitions'>Definitions</a></li> <ul> <li><a href='#undirected_graphs'>Undirected graphs</a></li> <li><a href='#directed_graphs'>Directed graphs</a></li> <li><a href='#undirected_graphs_as_directed_graphs_with_an_involution'>Undirected graphs as directed graphs with an involution</a></li> <li><a href='#orientations'>Orientations</a></li> </ul> <li><a href='#auxiliary_definitions'>Auxiliary definitions</a></li> <li><a href='#morphisms_of_graphs'>Morphisms of graphs</a></li> <li><a href='#notions_of_labeled_graphs'>Notions of labeled graphs</a></li> <li><a href='#notions_of_subgraphs_from_the_npov'>Notions of subgraphs from the nPOV</a></li> <li><a href='#undirected_graphs_as_1complexes_barycentric_subdivision'>Undirected graphs as 1-complexes, barycentric subdivision</a></li> <li><a href='#flavors_of_graphs'>Flavors of graphs</a></li> <li><a href='#lawveres_remarks_on_graph_theory'>Lawvere’s remarks on graph theory</a></li> <li><a href='#in_constructive_mathematics'>In constructive mathematics</a></li> <li><a href='#related_concepts'>Related concepts</a></li> <li><a href='#references'>References</a></li> </ul> </div> <h2 id="idea">Idea</h2> <p>A <strong>graph</strong> is a collection of <em><a class="existingWikiWord" href="/nlab/show/vertices">vertices</a></em> and <em><a class="existingWikiWord" href="/nlab/show/edges">edges</a></em>; each <a class="existingWikiWord" href="/nlab/show/edge">edge</a> links a pair of <a class="existingWikiWord" href="/nlab/show/vertices">vertices</a>, defining a relationship of <em>incidence</em> between vertices and edges. There are several variations on the idea, described below.</p> <p>This is the sense of graph in <a class="existingWikiWord" href="/nlab/show/combinatorics">combinatorics</a>; the other sense in high-school algebra, which interprets a <a class="existingWikiWord" href="/nlab/show/morphism">morphism</a> <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mi>f</mi><mo>:</mo><mi>A</mi><mo>→</mo><mi>B</mi></mrow><annotation encoding="application/x-tex">f: A \to B</annotation></semantics></math> as a <a class="existingWikiWord" href="/nlab/show/subobject">subobject</a> of the <a class="existingWikiWord" href="/nlab/show/product">product</a> <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mi>A</mi><mo>×</mo><mi>B</mi></mrow><annotation encoding="application/x-tex">A \times B</annotation></semantics></math>, is unrelated; see <em><a class="existingWikiWord" href="/nlab/show/graph+of+a+function">graph of a function</a></em> for more on this.</p> <h2 id="definitions">Definitions</h2> <p>Let <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mi>V</mi></mrow><annotation encoding="application/x-tex">V</annotation></semantics></math> and <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mi>E</mi></mrow><annotation encoding="application/x-tex">E</annotation></semantics></math> be <a class="existingWikiWord" href="/nlab/show/sets">sets</a>; call an element of <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mi>V</mi></mrow><annotation encoding="application/x-tex">V</annotation></semantics></math> a <strong>vertex</strong> and an element of <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mi>E</mi></mrow><annotation encoding="application/x-tex">E</annotation></semantics></math> an <strong>edge</strong>. A <strong>graph</strong> is given by <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mi>V</mi></mrow><annotation encoding="application/x-tex">V</annotation></semantics></math>, <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mi>E</mi></mrow><annotation encoding="application/x-tex">E</annotation></semantics></math>, and a mapping <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mi>d</mi></mrow><annotation encoding="application/x-tex">d</annotation></semantics></math> that interprets edges as pairs of vertices. Exactly what this means depends on how one defines ‘mapping that interprets’ and ‘pair’; the possibilities are given below. We will need the following notation:</p> <ul> <li><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><msup><mi>V</mi> <mn>2</mn></msup></mrow><annotation encoding="application/x-tex">V^2</annotation></semantics></math> is the <a class="existingWikiWord" href="/nlab/show/cartesian+product">cartesian product</a> of <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mi>V</mi></mrow><annotation encoding="application/x-tex">V</annotation></semantics></math> with itself, the set of ordered pairs <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mo stretchy="false">(</mo><mi>x</mi><mo>,</mo><mi>y</mi><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">(x,y)</annotation></semantics></math> of vertices;</li> <li><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><msub><mi>Δ</mi> <mi>V</mi></msub></mrow><annotation encoding="application/x-tex">\Delta_V</annotation></semantics></math> is the <a class="existingWikiWord" href="/nlab/show/diagonal+subset">diagonal subset</a> of <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mi>V</mi></mrow><annotation encoding="application/x-tex">V</annotation></semantics></math>, the set of pairs <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mo stretchy="false">(</mo><mi>x</mi><mo>,</mo><mi>x</mi><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">(x,x)</annotation></semantics></math>, so that its <a class="existingWikiWord" href="/nlab/show/complement">complement</a> <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><msup><mi>V</mi> <mn>2</mn></msup><mo>∖</mo><msub><mi>Δ</mi> <mi>V</mi></msub></mrow><annotation encoding="application/x-tex">V^2 \setminus \Delta_V</annotation></semantics></math> is the set of pairs as above where <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mi>x</mi><mo>≠</mo><mi>y</mi></mrow><annotation encoding="application/x-tex">x \neq y</annotation></semantics></math>;</li> <li><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mrow><mo>⟨</mo><mfrac linethickness="0"><mrow><mi>V</mi></mrow><mrow><mn>2</mn></mrow></mfrac><mo>⟩</mo></mrow></mrow><annotation encoding="application/x-tex">\left\langle{V \atop 2}\right\rangle</annotation></semantics></math> is the <a class="existingWikiWord" href="/nlab/show/quotient+set">quotient set</a> of <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><msup><mi>V</mi> <mn>2</mn></msup></mrow><annotation encoding="application/x-tex">V^2</annotation></semantics></math> in which <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mo stretchy="false">(</mo><mi>x</mi><mo>,</mo><mi>y</mi><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">(x,y)</annotation></semantics></math> is identified with <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mo stretchy="false">(</mo><mi>y</mi><mo>,</mo><mi>x</mi><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">(y,x)</annotation></semantics></math>, the set of unordered pairs <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mo stretchy="false">{</mo><mi>x</mi><mo>,</mo><mi>y</mi><mo stretchy="false">}</mo></mrow><annotation encoding="application/x-tex">\{x,y\}</annotation></semantics></math> of vertices;</li> <li><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mrow><mo>(</mo><mfrac linethickness="0"><mrow><mi>V</mi></mrow><mrow><mn>2</mn></mrow></mfrac><mo>)</mo></mrow></mrow><annotation encoding="application/x-tex">\left({V \atop 2}\right)</annotation></semantics></math> is the quotient set of <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><msup><mi>V</mi> <mn>2</mn></msup><mo>∖</mo><msub><mi>Δ</mi> <mi>V</mi></msub></mrow><annotation encoding="application/x-tex">V^2 \setminus \Delta_V</annotation></semantics></math> in which <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mo stretchy="false">(</mo><mi>x</mi><mo>,</mo><mi>y</mi><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">(x,y)</annotation></semantics></math> is identified with <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mo stretchy="false">(</mo><mi>y</mi><mo>,</mo><mi>x</mi><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">(y,x)</annotation></semantics></math>, the set of unordered pairs where <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mi>x</mi><mo>≠</mo><mi>y</mi></mrow><annotation encoding="application/x-tex">x \neq y</annotation></semantics></math>.</li> </ul> <h3 id="undirected_graphs">Undirected graphs</h3> <p>We are now ready for the first batch of definitions.</p> <ul> <li> <p>For a <strong>simple graph</strong>, a pair of vertices is a <a class="existingWikiWord" href="/nlab/show/subset">subset</a> of <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mi>V</mi></mrow><annotation encoding="application/x-tex">V</annotation></semantics></math> of <a class="existingWikiWord" href="/nlab/show/cardinality">cardinality</a> <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mn>2</mn></mrow><annotation encoding="application/x-tex">2</annotation></semantics></math>, and we interpret edges as unordered pairs of vertices in a one-to-one way. Thus a simple graph is given by <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mi>V</mi></mrow><annotation encoding="application/x-tex">V</annotation></semantics></math>, <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mi>E</mi></mrow><annotation encoding="application/x-tex">E</annotation></semantics></math>, and an <a class="existingWikiWord" href="/nlab/show/injective+function">injective function</a> <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mi>d</mi><mo>:</mo><mi>E</mi><mo>↪</mo><mrow><mo>(</mo><mfrac linethickness="0"><mrow><mi>V</mi></mrow><mrow><mn>2</mn></mrow></mfrac><mo>)</mo></mrow></mrow><annotation encoding="application/x-tex">d: E \hookrightarrow \left({V \atop 2}\right)</annotation></semantics></math>. Among graph theorists, this is often the default meaning of ‘graph’ unless another is specified. The category of simple graphs is called <a class="existingWikiWord" href="/nlab/show/category+of+simple+graphs">SimpGph</a></p> </li> <li> <p>For a <strong><a class="existingWikiWord" href="/nlab/show/multigraph">multigraph</a></strong>, a pair of vertices is the same as above, but we interpret edges as pairs of vertices in a many-to-one way. Thus a multigraph is given by <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mi>V</mi></mrow><annotation encoding="application/x-tex">V</annotation></semantics></math>, <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mi>E</mi></mrow><annotation encoding="application/x-tex">E</annotation></semantics></math>, and an arbitrary <a class="existingWikiWord" href="/nlab/show/function">function</a> <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mi>d</mi><mo>:</mo><mi>E</mi><mo>→</mo><mrow><mo>(</mo><mfrac linethickness="0"><mrow><mi>V</mi></mrow><mrow><mn>2</mn></mrow></mfrac><mo>)</mo></mrow></mrow><annotation encoding="application/x-tex">d: E \to \left({V \atop 2}\right)</annotation></semantics></math>.</p> </li> <li> <p>For a <strong>loop graph</strong>, a pair of vertices is any subset of the form <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mo stretchy="false">{</mo><mi>x</mi><mo>,</mo><mi>y</mi><mo stretchy="false">}</mo></mrow><annotation encoding="application/x-tex">\{x,y\}</annotation></semantics></math>, where <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mi>x</mi><mo>=</mo><mi>y</mi></mrow><annotation encoding="application/x-tex">x = y</annotation></semantics></math> is allowed, and we interpret edges as pairs of vertices in a one-to-one way again. Thus a loop-graph is given by <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mi>V</mi></mrow><annotation encoding="application/x-tex">V</annotation></semantics></math>, <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mi>E</mi></mrow><annotation encoding="application/x-tex">E</annotation></semantics></math>, and an injective function <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mi>d</mi><mo>:</mo><mi>E</mi><mo>↪</mo><mrow><mo>⟨</mo><mfrac linethickness="0"><mrow><mi>V</mi></mrow><mrow><mn>2</mn></mrow></mfrac><mo>⟩</mo></mrow></mrow><annotation encoding="application/x-tex">d: E \hookrightarrow \left\langle{V \atop 2}\right\rangle</annotation></semantics></math>.</p> </li> <li> <p>For a <strong><a class="existingWikiWord" href="/nlab/show/pseudograph">pseudograph</a></strong>, a pair of vertices is as in a loop graph, while edges are interpreted as pairs of vertices as in a multigraph. Thus a pseudograph is given by <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mi>V</mi></mrow><annotation encoding="application/x-tex">V</annotation></semantics></math>, <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mi>E</mi></mrow><annotation encoding="application/x-tex">E</annotation></semantics></math>, and a function <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mi>d</mi><mo>:</mo><mi>E</mi><mo>→</mo><mrow><mo>⟨</mo><mfrac linethickness="0"><mrow><mi>V</mi></mrow><mrow><mn>2</mn></mrow></mfrac><mo>⟩</mo></mrow></mrow><annotation encoding="application/x-tex">d: E \to \left\langle{V \atop 2}\right\rangle</annotation></semantics></math>.</p> </li> </ul> <p>Note: While ‘simple graph’ is unambiguous, the other terms above are not. In particular, ‘multigraph’ sometimes means a pseudograph, ‘pseudograph’ sometimes means a loop graph, and ‘loop graph’ sometimes means a pseudograph. These could be made unambiguous by saying ‘simple multigraph’, ‘simple loop graph’, and ‘multipseudograph’, respectively, but we will try to keep our terminology short. An oldfashioned (e.g. <a href="#Harary1953">p. 142</a>) term for ‘simple graph’ is ‘linear graph’, traces of which remain in the usual term ‘linear hypergraph’ in combinatorics (i.e. hypergraph any two edges of which intersect in at most one element of the ground set).</p> <h3 id="directed_graphs">Directed graphs</h3> <p>In all four of the above, edges are interpreted as <em>unordered</em> pairs. If we instead interpret edges as <em>ordered</em> pairs, then we get four new concepts:</p> <ul> <li>A <strong>directed graph</strong> consists of <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mi>V</mi></mrow><annotation encoding="application/x-tex">V</annotation></semantics></math>, <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mi>E</mi></mrow><annotation encoding="application/x-tex">E</annotation></semantics></math>, and an injective function <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mi>d</mi><mo>:</mo><mi>E</mi><mo>↪</mo><msup><mi>V</mi> <mn>2</mn></msup><mo>∖</mo><msub><mi>Δ</mi> <mi>V</mi></msub></mrow><annotation encoding="application/x-tex">d: E \hookrightarrow V^2 \setminus \Delta_V</annotation></semantics></math>;</li> <li>a <strong>directed multigraph</strong> consists of <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mi>V</mi></mrow><annotation encoding="application/x-tex">V</annotation></semantics></math>, <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mi>E</mi></mrow><annotation encoding="application/x-tex">E</annotation></semantics></math>, and a function <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mi>d</mi><mo>:</mo><mi>E</mi><mo>→</mo><msup><mi>V</mi> <mn>2</mn></msup><mo>∖</mo><msub><mi>Δ</mi> <mi>V</mi></msub></mrow><annotation encoding="application/x-tex">d: E \to V^2 \setminus \Delta_V</annotation></semantics></math>;</li> <li>a <strong>directed loop graph</strong> consists of <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mi>V</mi></mrow><annotation encoding="application/x-tex">V</annotation></semantics></math>, <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mi>E</mi></mrow><annotation encoding="application/x-tex">E</annotation></semantics></math>, and an injective function <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mi>d</mi><mo>:</mo><mi>E</mi><mo>↪</mo><msup><mi>V</mi> <mn>2</mn></msup></mrow><annotation encoding="application/x-tex">d: E \hookrightarrow V^2</annotation></semantics></math>;</li> <li>a <strong><a class="existingWikiWord" href="/nlab/show/directed+pseudograph">directed pseudograph</a></strong> consists of <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mi>V</mi></mrow><annotation encoding="application/x-tex">V</annotation></semantics></math>, <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mi>E</mi></mrow><annotation encoding="application/x-tex">E</annotation></semantics></math>, and a function <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mi>d</mi><mo>:</mo><mi>E</mi><mo>→</mo><msup><mi>V</mi> <mn>2</mn></msup></mrow><annotation encoding="application/x-tex">d: E \to V^2</annotation></semantics></math>.</li> </ul> <p>Directed pseudographs are commonly used in <a class="existingWikiWord" href="/nlab/show/category+theory">category theory</a>, where they are often called ‘directed graphs’, ‘digraphs’, (less ambiguously) ‘<a class="existingWikiWord" href="/nlab/show/quivers">quivers</a>’, or often in fact simply ‘graphs’.</p> <p>The same terminological ambiguities as above apply here as well, and they can be resolved in the same way, including using ‘simple directed graph’ for a directed graph if necessary. One can also use ‘undirected’ in place of ‘directed’ to emphasise that the previous definitions apply instead of these.</p> <p>It is always possible to interpret any kind of graph as a directed pseudograph (a quiver), in which there happens to be at most one edge between a given pair of vertices, or there happen to be no loops (or alternatively exactly one of every possible kind of loop), or in which there is an edge from <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mi>x</mi></mrow><annotation encoding="application/x-tex">x</annotation></semantics></math> to <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mi>y</mi></mrow><annotation encoding="application/x-tex">y</annotation></semantics></math> if and only if there is an edge from <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mi>y</mi></mrow><annotation encoding="application/x-tex">y</annotation></semantics></math> to <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mi>x</mi></mrow><annotation encoding="application/x-tex">x</annotation></semantics></math>, or some mixture of these.</p> <h3 id="undirected_graphs_as_directed_graphs_with_an_involution">Undirected graphs as directed graphs with an involution</h3> <p>There is an alternative definition of an undirected graph allowing loops and multiple edges (cf. <a href="#Serre1977">Serre 1977</a>), that begins with the structure of a quiver <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mi>s</mi><mo>,</mo><mi>t</mi><mo>:</mo><mi>E</mi><mo>⇉</mo><mi>V</mi></mrow><annotation encoding="application/x-tex">s,t : E \rightrightarrows V</annotation></semantics></math> and then asks in addition for a <a class="existingWikiWord" href="/nlab/show/fixed+point">fixed point</a> free <a class="existingWikiWord" href="/nlab/show/involution">involution</a> on edges <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mi>i</mi><mo>:</mo><mi>E</mi><mo>→</mo><mi>E</mi></mrow><annotation encoding="application/x-tex">i : E \to E</annotation></semantics></math> swapping source and target, i.e., such that</p> <div class="maruku-equation"><math xmlns="http://www.w3.org/1998/Math/MathML" display="block" class="maruku-mathml"><semantics><mrow><mi>i</mi><mo stretchy="false">(</mo><mi>i</mi><mo stretchy="false">(</mo><mi>e</mi><mo stretchy="false">)</mo><mo stretchy="false">)</mo><mo>=</mo><mi>e</mi><mspace width="1em"></mspace><mi>i</mi><mo stretchy="false">(</mo><mi>e</mi><mo stretchy="false">)</mo><mo>≠</mo><mi>e</mi><mspace width="1em"></mspace><mi>s</mi><mo stretchy="false">(</mo><mi>i</mi><mo stretchy="false">(</mo><mi>e</mi><mo stretchy="false">)</mo><mo stretchy="false">)</mo><mo>=</mo><mi>t</mi><mo stretchy="false">(</mo><mi>e</mi><mo stretchy="false">)</mo><mspace width="1em"></mspace><mi>t</mi><mo stretchy="false">(</mo><mi>i</mi><mo stretchy="false">(</mo><mi>e</mi><mo stretchy="false">)</mo><mo stretchy="false">)</mo><mo>=</mo><mi>s</mi><mo stretchy="false">(</mo><mi>e</mi><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex"> i(i(e)) = e \quad i(e) \ne e \quad s(i(e)) = t(e) \quad t(i(e)) = s(e) </annotation></semantics></math></div> <p>Of course, since the source <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mi>s</mi><mo>:</mo><mi>E</mi><mo>→</mo><mi>V</mi></mrow><annotation encoding="application/x-tex">s : E \to V</annotation></semantics></math> and target <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mi>t</mi><mo>:</mo><mi>E</mi><mo>→</mo><mi>V</mi></mrow><annotation encoding="application/x-tex">t : E \to V</annotation></semantics></math> functions determine each other in the presence of the involution <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mi>i</mi><mo>:</mo><mi>E</mi><mo>→</mo><mi>E</mi></mrow><annotation encoding="application/x-tex">i : E \to E</annotation></semantics></math>, it is enough to give, say, <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mi>s</mi></mrow><annotation encoding="application/x-tex">s</annotation></semantics></math> and <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mi>i</mi></mrow><annotation encoding="application/x-tex">i</annotation></semantics></math> to define an undirected graph. In that case, one might alternatively view <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mi>E</mi></mrow><annotation encoding="application/x-tex">E</annotation></semantics></math> as a set of “half-edges” or “flags” (with <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mi>i</mi></mrow><annotation encoding="application/x-tex">i</annotation></semantics></math> the involution swapping the two halves of an edge), and even lift the condition that <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mi>i</mi></mrow><annotation encoding="application/x-tex">i</annotation></semantics></math> has no fixed points to allow for the possibility of undirected graphs with “dangling” or “open” edges (i.e., with only one side attached to a vertex).</p> <p>Although this definition of undirected graphs with open edges is standard (cf. <a class="existingWikiWord" href="/nlab/show/ribbon+graph">ribbon graph</a>), <a href="#Kock2016BM">Kock (2016b)</a> remarks that “it does not naturally lead to good notions of morphisms, beyond isomorphisms”. A slight variation of this definition with a more natural notion of morphism was introduced by <a href="#JoyalKockQPL">Joyal and Kock (2009)</a>: they define a “Feynman graph” as a triple of <a class="existingWikiWord" href="/nlab/show/finite+sets">finite sets</a> <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mi>V</mi><mo>,</mo><mi>E</mi><mo>,</mo><mi>H</mi></mrow><annotation encoding="application/x-tex">V, E, H</annotation></semantics></math> together with a triple of a function <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mi>t</mi><mo>:</mo><mi>H</mi><mo>→</mo><mi>V</mi></mrow><annotation encoding="application/x-tex">t : H \to V</annotation></semantics></math>, an injection <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mi>s</mi><mo>:</mo><mi>H</mi><mo>→</mo><mi>E</mi></mrow><annotation encoding="application/x-tex">s : H \to E</annotation></semantics></math>, and a fixed point free involution <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mi>i</mi><mo>:</mo><mi>E</mi><mo>→</mo><mi>E</mi></mrow><annotation encoding="application/x-tex">i : E \to E</annotation></semantics></math>. (See also <a href="#Kock2016GHP">Kock (2016a)</a> for further discussion.)</p> <h3 id="orientations">Orientations</h3> <p>An <strong>orientation</strong> of an undirected graph is the choice of a direction for every edge. Formally, if we define undirected graphs as above to be quivers <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mi>E</mi><mo>⇉</mo><mi>V</mi></mrow><annotation encoding="application/x-tex">E \rightrightarrows V</annotation></semantics></math> equipped with a fixed point free involution <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mi>i</mi><mo>:</mo><mi>E</mi><mo>→</mo><mi>E</mi></mrow><annotation encoding="application/x-tex">i : E \to E</annotation></semantics></math>, then an orientation corresponds to the choice of a subset <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><msup><mi>E</mi> <mo>+</mo></msup><mo>⊆</mo><mi>E</mi></mrow><annotation encoding="application/x-tex">E^+ \subseteq E</annotation></semantics></math> such that <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mi>E</mi></mrow><annotation encoding="application/x-tex">E</annotation></semantics></math> is the <a class="existingWikiWord" href="/nlab/show/disjoint+union">disjoint union</a> <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mi>E</mi><mo>=</mo><msup><mi>E</mi> <mo>+</mo></msup><mo>⊎</mo><mi>i</mi><mo stretchy="false">(</mo><msup><mi>E</mi> <mo>+</mo></msup><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">E = E^+ \uplus i(E^+)</annotation></semantics></math>.</p> <p>Any orientation of an undirected graph induces a corresponding directed graph <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><msup><mi>E</mi> <mo>+</mo></msup><mo>⇉</mo><mi>V</mi></mrow><annotation encoding="application/x-tex">E^+ \rightrightarrows V</annotation></semantics></math>. In many situations, though, it is useful to consider a given undirected graph equipped with one of many possible orientations. For example, various <span class="newWikiWord">graph invariants<a href="/nlab/new/graph+invariants">?</a></span> (such as the <span class="newWikiWord">flow polynomial<a href="/nlab/new/flow+polynomial">?</a></span>, or <a class="existingWikiWord" href="/nlab/show/W.+T.+Tutte">Tutte</a>‘s original definition of the <span class="newWikiWord">Tutte polynomial<a href="/nlab/new/Tutte+polynomial">?</a></span>) can be defined for an arbitrary orientation of a graph, but are independent of the choice of orientation.</p> <h2 id="auxiliary_definitions">Auxiliary definitions</h2> <p>The term <strong>arc</strong> is often used for an <em>ordered</em> edge, while <strong>line</strong> is sometimes used for an <em>unordered</em> edge. We say that an arc <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mi>e</mi></mrow><annotation encoding="application/x-tex">e</annotation></semantics></math> with <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mi>d</mi><mo stretchy="false">(</mo><mi>e</mi><mo stretchy="false">)</mo><mo>=</mo><mo stretchy="false">(</mo><mi>x</mi><mo>,</mo><mi>y</mi><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">d(e) = (x,y)</annotation></semantics></math> is an arc <strong>from <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mi>x</mi></mrow><annotation encoding="application/x-tex">x</annotation></semantics></math> to <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mi>y</mi></mrow><annotation encoding="application/x-tex">y</annotation></semantics></math></strong>, while a line <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mi>e</mi></mrow><annotation encoding="application/x-tex">e</annotation></semantics></math> such that <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mi>d</mi><mo stretchy="false">(</mo><mi>e</mi><mo stretchy="false">)</mo><mo>=</mo><mo stretchy="false">{</mo><mi>x</mi><mo>,</mo><mi>y</mi><mo stretchy="false">}</mo></mrow><annotation encoding="application/x-tex">d(e) = \{x,y\}</annotation></semantics></math> is a line <strong>between <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mi>x</mi></mrow><annotation encoding="application/x-tex">x</annotation></semantics></math> and <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mi>y</mi></mrow><annotation encoding="application/x-tex">y</annotation></semantics></math></strong>. In either case, a <strong>loop</strong> is an edge from a vertex to itself or between a vertex and itself; only (possibly directed) loop graphs and pseudographs can have loops.</p> <p>Given any sort of graph, we can define a <a class="existingWikiWord" href="/nlab/show/binary+relation">binary relation</a> on <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mi>V</mi></mrow><annotation encoding="application/x-tex">V</annotation></semantics></math>; say that <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mi>x</mi></mrow><annotation encoding="application/x-tex">x</annotation></semantics></math> and <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mi>y</mi></mrow><annotation encoding="application/x-tex">y</annotation></semantics></math> are <strong>adjacent</strong>, written <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mi>x</mi><mo>∼</mo><mi>y</mi></mrow><annotation encoding="application/x-tex">x \sim y</annotation></semantics></math>, if there exists an edge <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mi>e</mi></mrow><annotation encoding="application/x-tex">e</annotation></semantics></math> such that <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mi>d</mi><mo stretchy="false">(</mo><mi>e</mi><mo stretchy="false">)</mo><mo>=</mo><mo stretchy="false">(</mo><mi>x</mi><mo>,</mo><mi>y</mi><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">d(e) = (x,y)</annotation></semantics></math> or <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mi>d</mi><mo stretchy="false">(</mo><mi>e</mi><mo stretchy="false">)</mo><mo>=</mo><mo stretchy="false">{</mo><mi>x</mi><mo>,</mo><mi>y</mi><mo stretchy="false">}</mo></mrow><annotation encoding="application/x-tex">d(e) = \{x,y\}</annotation></semantics></math>. A directed loop graph is determined entirely by this relation; we may say that it <em>is</em> <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mi>V</mi></mrow><annotation encoding="application/x-tex">V</annotation></semantics></math> equipped with a binary relation. Then a simple directed graph is <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mi>V</mi></mrow><annotation encoding="application/x-tex">V</annotation></semantics></math> equipped with an <a class="existingWikiWord" href="/nlab/show/irreflexive+relation">irreflexive relation</a> (or equivalently a <a class="existingWikiWord" href="/nlab/show/reflexive+relation">reflexive relation</a>), and an undirected loop graph is <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mi>V</mi></mrow><annotation encoding="application/x-tex">V</annotation></semantics></math> equipped with a <a class="existingWikiWord" href="/nlab/show/symmetric+relation">symmetric relation</a>.</p> <p>A graph is <strong><a class="existingWikiWord" href="/nlab/show/finite+graph">finite</a></strong> if <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mi>V</mi></mrow><annotation encoding="application/x-tex">V</annotation></semantics></math> and <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mi>E</mi></mrow><annotation encoding="application/x-tex">E</annotation></semantics></math> are both <a class="existingWikiWord" href="/nlab/show/finite+sets">finite sets</a>. Given a <a class="existingWikiWord" href="/nlab/show/linear+ordering">linear ordering</a> of the <a class="existingWikiWord" href="/nlab/show/vertices">vertices</a> of a <a class="existingWikiWord" href="/nlab/show/finite+graph">finite graph</a>, its <strong>adjacency matrix</strong> is a square <a class="existingWikiWord" href="/nlab/show/matrix">matrix</a> whose <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mo stretchy="false">(</mo><mi>i</mi><mo>,</mo><mi>j</mi><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">(i,j)</annotation></semantics></math>th entry gives the number of edges <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mi>e</mi></mrow><annotation encoding="application/x-tex">e</annotation></semantics></math> between the <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mi>i</mi></mrow><annotation encoding="application/x-tex">i</annotation></semantics></math>th and <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mi>j</mi></mrow><annotation encoding="application/x-tex">j</annotation></semantics></math>th vertices or from the <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mi>i</mi></mrow><annotation encoding="application/x-tex">i</annotation></semantics></math>th vertex to the <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mi>j</mi></mrow><annotation encoding="application/x-tex">j</annotation></semantics></math>th vertex. In the examples above where a graph is determined by a binary relation on <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mi>V</mi></mrow><annotation encoding="application/x-tex">V</annotation></semantics></math>, then matrix multiplication gives composition of relations.</p> <h2 id="morphisms_of_graphs">Morphisms of graphs</h2> <p>An <strong><a class="existingWikiWord" href="/nlab/show/isomorphism">isomorphism</a></strong> from <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mi>G</mi><mo>=</mo><mo stretchy="false">(</mo><mi>V</mi><mo>,</mo><mi>E</mi><mo>,</mo><mi>d</mi><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">G = (V,E,d)</annotation></semantics></math> to <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mi>G</mi><mo>′</mo><mo>=</mo><mo stretchy="false">(</mo><mi>V</mi><mo>′</mo><mo>,</mo><mi>E</mi><mo>′</mo><mo>,</mo><mi>d</mi><mo>′</mo><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">G' = (V',E',d')</annotation></semantics></math> consists of a bijection <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mi>f</mi><mo>:</mo><mi>V</mi><mo>→</mo><mi>V</mi><mo>′</mo></mrow><annotation encoding="application/x-tex">f: V \to V'</annotation></semantics></math>, together with a bijection from <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mi>E</mi></mrow><annotation encoding="application/x-tex">E</annotation></semantics></math> to <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mi>E</mi><mo>′</mo></mrow><annotation encoding="application/x-tex">E'</annotation></semantics></math> (also denoted <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mi>f</mi></mrow><annotation encoding="application/x-tex">f</annotation></semantics></math>) such that <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mi>f</mi></mrow><annotation encoding="application/x-tex">f</annotation></semantics></math> commutes with <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mi>d</mi></mrow><annotation encoding="application/x-tex">d</annotation></semantics></math>; that is, <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mi>d</mi><mo stretchy="false">(</mo><mi>f</mi><mo stretchy="false">(</mo><mi>e</mi><mo stretchy="false">)</mo><mo stretchy="false">)</mo><mo>=</mo><mo stretchy="false">(</mo><mi>f</mi><mo stretchy="false">(</mo><mi>x</mi><mo stretchy="false">)</mo><mo>,</mo><mi>f</mi><mo stretchy="false">(</mo><mi>y</mi><mo stretchy="false">)</mo><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">d(f(e)) = (f(x),f(y))</annotation></semantics></math> or <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mi>d</mi><mo stretchy="false">(</mo><mi>f</mi><mo stretchy="false">(</mo><mi>e</mi><mo stretchy="false">)</mo><mo stretchy="false">)</mo><mo>=</mo><mo stretchy="false">{</mo><mi>f</mi><mo stretchy="false">(</mo><mi>x</mi><mo stretchy="false">)</mo><mo>,</mo><mi>f</mi><mo stretchy="false">(</mo><mi>y</mi><mo stretchy="false">)</mo><mo stretchy="false">}</mo></mrow><annotation encoding="application/x-tex">d(f(e)) = \{f(x),f(y)\}</annotation></semantics></math> whenever <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mi>d</mi><mo stretchy="false">(</mo><mi>e</mi><mo stretchy="false">)</mo><mo>=</mo><mo stretchy="false">(</mo><mi>x</mi><mo>,</mo><mi>y</mi><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">d(e) = (x,y)</annotation></semantics></math> or <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mi>d</mi><mo stretchy="false">(</mo><mi>e</mi><mo stretchy="false">)</mo><mo>=</mo><mo stretchy="false">{</mo><mi>x</mi><mo>,</mo><mi>y</mi><mo stretchy="false">}</mo></mrow><annotation encoding="application/x-tex">d(e) = \{x,y\}</annotation></semantics></math> (as appropriate). Two graphs <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mi>G</mi></mrow><annotation encoding="application/x-tex">G</annotation></semantics></math> and <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mi>G</mi><mo>′</mo></mrow><annotation encoding="application/x-tex">G'</annotation></semantics></math> are <strong>isomorphic</strong> if there exists such an isomorphism. Then <a class="existingWikiWord" href="/nlab/show/finite+graphs">finite graphs</a> <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mi>G</mi></mrow><annotation encoding="application/x-tex">G</annotation></semantics></math> and <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mi>G</mi><mo>′</mo></mrow><annotation encoding="application/x-tex">G'</annotation></semantics></math> are isomorphic if and only if they have the same number of vertices and, for some ordering of their vertices, they have the same adjacency matrix.</p> <p>A <strong><a class="existingWikiWord" href="/nlab/show/morphism">morphism</a></strong> from <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mi>G</mi></mrow><annotation encoding="application/x-tex">G</annotation></semantics></math> to <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mi>G</mi><mo>′</mo></mrow><annotation encoding="application/x-tex">G'</annotation></semantics></math> should consist of functions <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mi>f</mi><mo>:</mo><mi>V</mi><mo>→</mo><mi>V</mi><mo>′</mo></mrow><annotation encoding="application/x-tex">f: V \to V'</annotation></semantics></math> and <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mi>f</mi><mo>:</mo><mi>E</mi><mo>→</mo><mi>E</mi><mo>′</mo></mrow><annotation encoding="application/x-tex">f: E \to E'</annotation></semantics></math> such that <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mi>f</mi></mrow><annotation encoding="application/x-tex">f</annotation></semantics></math> commutes with <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mi>d</mi></mrow><annotation encoding="application/x-tex">d</annotation></semantics></math>. However, some authors allow <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mi>f</mi><mo stretchy="false">(</mo><mi>e</mi><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">f(e)</annotation></semantics></math> to be undefined if <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mi>d</mi><mo stretchy="false">(</mo><mi>e</mi><mo stretchy="false">)</mo><mo>=</mo><mo stretchy="false">(</mo><mi>x</mi><mo>,</mo><mi>y</mi><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">d(e) = (x,y)</annotation></semantics></math> or <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mi>d</mi><mo stretchy="false">(</mo><mi>e</mi><mo stretchy="false">)</mo><mo>=</mo><mo stretchy="false">{</mo><mi>x</mi><mo>,</mo><mi>y</mi><mo stretchy="false">}</mo></mrow><annotation encoding="application/x-tex">d(e) = \{x,y\}</annotation></semantics></math> but <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mi>f</mi><mo stretchy="false">(</mo><mi>x</mi><mo stretchy="false">)</mo><mo>=</mo><mi>f</mi><mo stretchy="false">(</mo><mi>y</mi><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">f(x) = f(y)</annotation></semantics></math> when using a notion of graph where loops are forbidden. The difference amounts to whether one interprets a simple graph as a special kind of loop graph in which no loops exist (the first kind of morphism) or in which each vertex has a unique loop (the second kind of morphism). Either way, an isomorphism (as defined above) is precisely an invertible morphism.</p> <p>Under the second notion of morphism (where simple graphs are identified with sets equipped with a symmetric reflexive relation), the <a class="existingWikiWord" href="/nlab/show/category+of+simple+graphs">category of simple graphs</a> has many desirable properties (q.v.).</p> <h2 id="notions_of_labeled_graphs">Notions of labeled graphs</h2> <p>The <a class="existingWikiWord" href="/nlab/show/commutative+diagram">commutative diagrams</a> one sees in texts on category theory or on the nLab are often examples of <em>labeled graphs</em> i.e. basically quivers with names attached to their directed edges. These can be described in categorical terms:</p> <p>Consider the obvious inclusion <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mi>i</mi></mrow><annotation encoding="application/x-tex">i</annotation></semantics></math> of the one morphism category <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mi>A</mi></mrow><annotation encoding="application/x-tex">A</annotation></semantics></math> into the category <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mi>N</mi><mo>⇉</mo><mi>A</mi></mrow><annotation encoding="application/x-tex">N\rightrightarrows A</annotation></semantics></math> underlying the topos <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mi>Grph</mi></mrow><annotation encoding="application/x-tex">Grph</annotation></semantics></math> of <a class="existingWikiWord" href="/nlab/show/quiver">quivers</a>. This induces an <a class="existingWikiWord" href="/nlab/show/level">essential localisation</a> <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><msub><mi>i</mi> <mo>!</mo></msub><mo>⊣</mo><msup><mi>i</mi> <mo>*</mo></msup><mo>⊣</mo><msub><mi>i</mi> <mo>*</mo></msub><mo lspace="verythinmathspace">:</mo><mi>Set</mi><mo>↪</mo><mi>Grph</mi></mrow><annotation encoding="application/x-tex">i_!\dashv i^*\dashv i_*\colon Set \hookrightarrow Grph</annotation></semantics></math>.</p> <p>Here <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><msub><mi>i</mi> <mo>*</mo></msub></mrow><annotation encoding="application/x-tex">i_*</annotation></semantics></math> interprets a set <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mi>X</mi></mrow><annotation encoding="application/x-tex">X</annotation></semantics></math> as the one node graph with arc set <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mi>X</mi></mrow><annotation encoding="application/x-tex">X</annotation></semantics></math>, whereas <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><msup><mi>i</mi> <mo>*</mo></msup></mrow><annotation encoding="application/x-tex">i^*</annotation></semantics></math> maps a graph <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mi>G</mi></mrow><annotation encoding="application/x-tex">G</annotation></semantics></math> to its arc set <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mi>G</mi><mo stretchy="false">[</mo><mi>A</mi><mo stretchy="false">]</mo></mrow><annotation encoding="application/x-tex">G[A]</annotation></semantics></math> and <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><msub><mi>i</mi> <mo>!</mo></msub></mrow><annotation encoding="application/x-tex">i_!</annotation></semantics></math> maps a set <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mi>X</mi></mrow><annotation encoding="application/x-tex">X</annotation></semantics></math> to the graph with node set <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mo stretchy="false">{</mo><mi>src</mi><mo>,</mo><mi>trg</mi><mo stretchy="false">}</mo><mo>×</mo><mi>X</mi></mrow><annotation encoding="application/x-tex">\{src,trg\}\times X</annotation></semantics></math> where <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mi>x</mi><mo>∈</mo><mi>X</mi></mrow><annotation encoding="application/x-tex">x\in X</annotation></semantics></math> becomes now an arc <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mi>x</mi></mrow><annotation encoding="application/x-tex">x</annotation></semantics></math> from <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mo stretchy="false">(</mo><mi>src</mi><mo>,</mo><mi>x</mi><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">(src,x)</annotation></semantics></math> to <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mo stretchy="false">(</mo><mi>trg</mi><mo>,</mo><mi>x</mi><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">(trg,x)</annotation></semantics></math>.</p> <p>The <a class="existingWikiWord" href="/nlab/show/slice+topos">slice topos</a> <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mi>Grph</mi><mo stretchy="false">/</mo><msub><mi>i</mi> <mo>*</mo></msub><mo stretchy="false">(</mo><mi>L</mi><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">Grph/i_*(L)</annotation></semantics></math> then the yields a first notion of a graph labelled by the set <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mi>L</mi></mrow><annotation encoding="application/x-tex">L</annotation></semantics></math> of labels. Since this slice is equivalent to the <a class="existingWikiWord" href="/nlab/show/category+of+elements">category of elements</a> of <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mi>Hom</mi><mo stretchy="false">(</mo><mo lspace="verythinmathspace" rspace="0em">−</mo><mo>,</mo><msub><mi>i</mi> <mo>*</mo></msub><mo stretchy="false">(</mo><mi>L</mi><mo stretchy="false">)</mo><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">Hom(-,i_*(L))</annotation></semantics></math> the projection <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mi>π</mi><mo lspace="verythinmathspace">:</mo><mi>Grph</mi><mo stretchy="false">/</mo><msub><mi>i</mi> <mo>*</mo></msub><mo stretchy="false">(</mo><mi>L</mi><mo stretchy="false">)</mo><mo>→</mo><mi>Grph</mi></mrow><annotation encoding="application/x-tex">\pi\colon Grph/i_*(L)\to Grph</annotation></semantics></math> is a <a class="existingWikiWord" href="/nlab/show/fibration">fibration</a>.</p> <p>Since the <a class="existingWikiWord" href="/nlab/show/separated+object">separated objects</a> for the <a class="existingWikiWord" href="/nlab/show/double+negation">double negation topology</a> on <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mi>Grph</mi><mo stretchy="false">/</mo><msub><mi>i</mi> <mo>*</mo></msub><mo stretchy="false">(</mo><mi>L</mi><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">Grph/i_*(L)</annotation></semantics></math> are exactly the L-labeled graphs with no parallel arcs receiving the same label, the <a class="existingWikiWord" href="/nlab/show/quasitopos">quasitopos</a> of all these graphs can be identified with the category of a labeled transition systems over alphabet <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mi>L</mi></mrow><annotation encoding="application/x-tex">L</annotation></semantics></math> familiar from <a class="existingWikiWord" href="/nlab/show/automaton">automata theory</a> (cf. <a href="#Vigna97">Vigna</a>, p.8).</p> <p>The above slice construction keeps the label set <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mi>L</mi></mrow><annotation encoding="application/x-tex">L</annotation></semantics></math> fixed but if one wants to consider all possible labelings at once, application of <a class="existingWikiWord" href="/nlab/show/Artin+gluing">Artin gluing</a> to <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><msub><mi>i</mi> <mo>*</mo></msub><mo lspace="verythinmathspace">:</mo><mi>Set</mi><mo>→</mo><mi>Grph</mi></mrow><annotation encoding="application/x-tex">i_*\colon Set\to Grph</annotation></semantics></math> provides the appropriate topos <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mi>Grph</mi><mo stretchy="false">↓</mo><msub><mi>i</mi> <mo>*</mo></msub></mrow><annotation encoding="application/x-tex">Grph\downarrow i_*</annotation></semantics></math>: This has objects <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mo stretchy="false">(</mo><mi>L</mi><mo>,</mo><mi>G</mi><mo>,</mo><mi>l</mi><mo>:</mo><mi>G</mi><mo>→</mo><msub><mi>i</mi> <mo>*</mo></msub><mo stretchy="false">(</mo><mi>L</mi><mo stretchy="false">)</mo><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">(L,G,l:G\to i_*(L))</annotation></semantics></math> where <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mi>L</mi></mrow><annotation encoding="application/x-tex">L</annotation></semantics></math> is the set of “labels”, <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mi>G</mi></mrow><annotation encoding="application/x-tex">G</annotation></semantics></math> a graph and the graph homorphism <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mi>l</mi></mrow><annotation encoding="application/x-tex">l</annotation></semantics></math> a labelling of <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mi>G</mi></mrow><annotation encoding="application/x-tex">G</annotation></semantics></math>. A morphism <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><msub><mi>X</mi> <mn>1</mn></msub><mo>→</mo><msub><mi>X</mi> <mn>2</mn></msub></mrow><annotation encoding="application/x-tex">X_1\to X_2</annotation></semantics></math> is a pair of maps <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mo stretchy="false">(</mo><mi>f</mi><mo>:</mo><msub><mi>L</mi> <mn>1</mn></msub><mo>→</mo><msub><mi>L</mi> <mn>2</mn></msub><mo>,</mo><mi>g</mi><mo>:</mo><msub><mi>G</mi> <mn>1</mn></msub><mo>→</mo><msub><mi>G</mi> <mn>2</mn></msub><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">(f:L_1\to L_2, g:G_1\to G_2)</annotation></semantics></math> satisfying <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><msub><mi>i</mi> <mo>*</mo></msub><mo stretchy="false">(</mo><mi>f</mi><mo stretchy="false">)</mo><mo>∘</mo><msub><mi>l</mi> <mn>1</mn></msub><mo>=</mo><msub><mi>l</mi> <mn>2</mn></msub><mo>∘</mo><mi>g</mi></mrow><annotation encoding="application/x-tex">i_*(f)\circ l_1 = l_2\circ g</annotation></semantics></math>.</p> <p>By general facts on <a class="existingWikiWord" href="/nlab/show/Artin+gluing">Artin gluing</a>, <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mi>Grph</mi><mo stretchy="false">↓</mo><msub><mi>i</mi> <mo>*</mo></msub></mrow><annotation encoding="application/x-tex">Grph\downarrow i_*</annotation></semantics></math> comes equipped with two <a class="existingWikiWord" href="/nlab/show/subtopos">subtopos inclusions</a> <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mi>Set</mi><mo>↪</mo><mi>Grph</mi><mo stretchy="false">↓</mo><msub><mi>i</mi> <mo>*</mo></msub></mrow><annotation encoding="application/x-tex">Set\hookrightarrow Grph\downarrow i_*</annotation></semantics></math> and <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mi>Grph</mi><mo>↪</mo><mi>Grph</mi><mo stretchy="false">↓</mo><msub><mi>i</mi> <mo>*</mo></msub></mrow><annotation encoding="application/x-tex">Grph\hookrightarrow Grph\downarrow i_*</annotation></semantics></math>, the first one being an <a class="existingWikiWord" href="/nlab/show/open+geometric+morphism">open geometric morphism</a> with <a class="existingWikiWord" href="/nlab/show/inverse+image">inverse image</a> projection a <a class="existingWikiWord" href="/nlab/show/logical+morphism">logical morphism</a> as well as a <a class="existingWikiWord" href="/nlab/show/fibration">fibration</a> (cf. <a class="existingWikiWord" href="/nlab/show/Elephant">Elephant</a>, B1.3.7(b), p.269) whereas the latter is <a class="existingWikiWord" href="/nlab/show/closed+subtopos">closed</a>.</p> <p>Nothing here hinges on <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><msub><mi>i</mi> <mo>*</mo></msub></mrow><annotation encoding="application/x-tex">i_*</annotation></semantics></math> being <a class="existingWikiWord" href="/nlab/show/fully+faithful">fully faithful</a> (cf. <a href="#Law89">Lawvere</a>, p.278) or its exactness properties though the resulting <a class="existingWikiWord" href="/nlab/show/comma+category">comma category</a> might loose some of its good properties for more general functors <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mi>i</mi></mrow><annotation encoding="application/x-tex">i</annotation></semantics></math> e.g. <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mi>Grph</mi><mo stretchy="false">↓</mo><msub><mi>i</mi> <mo>!</mo></msub></mrow><annotation encoding="application/x-tex">Grph\downarrow i_!</annotation></semantics></math> provides a category of loopless labelled graphs.</p> <p>If one would (more unusually) like to label <em>nodes</em> instead of arcs, one can consider the inclusion <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mi>j</mi></mrow><annotation encoding="application/x-tex">j</annotation></semantics></math> of <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mi>N</mi></mrow><annotation encoding="application/x-tex">N</annotation></semantics></math> into <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mi>N</mi><mo>⇉</mo><mi>A</mi></mrow><annotation encoding="application/x-tex">N\rightrightarrows A</annotation></semantics></math> instead of the above <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mi>i</mi></mrow><annotation encoding="application/x-tex">i</annotation></semantics></math>. This induces the complementary (essential) subtopos inclusion <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><msub><mi>Grph</mi> <mrow><mo>¬</mo><mo>¬</mo></mrow></msub><mo>↪</mo><mi>Grph</mi></mrow><annotation encoding="application/x-tex">Grph_{\neg\neg}\hookrightarrow Grph</annotation></semantics></math> where <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><msub><mi>j</mi> <mo>*</mo></msub></mrow><annotation encoding="application/x-tex">j_*</annotation></semantics></math> now reinterprets a set <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mi>X</mi></mrow><annotation encoding="application/x-tex">X</annotation></semantics></math> as the complete graph on node set <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mi>X</mi></mrow><annotation encoding="application/x-tex">X</annotation></semantics></math> whence labeling graph morphisms <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mi>G</mi><mo>→</mo><msub><mi>j</mi> <mo>*</mo></msub><mo stretchy="false">(</mo><mi>L</mi><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">G\to j_*(L)</annotation></semantics></math> pick up labels drawn from <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mi>L</mi></mrow><annotation encoding="application/x-tex">L</annotation></semantics></math> for the nodes of <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mi>G</mi></mrow><annotation encoding="application/x-tex">G</annotation></semantics></math> this time.</p> <h2 id="notions_of_subgraphs_from_the_npov">Notions of subgraphs from the nPOV</h2> <p>A usual definition of <em>subgraph</em> in combinatorics is, roughly: <em>subset</em>. More precisely, if <em>undirected simple graph</em> means <em>pair <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mo stretchy="false">(</mo><mi>V</mi><mo>,</mo><mi>E</mi><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">(V,E)</annotation></semantics></math> of two sets, with <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mi>E</mi><mo>⊆</mo><mo stretchy="false">[</mo><mi>V</mi><msup><mo stretchy="false">]</mo> <mn>2</mn></msup></mrow><annotation encoding="application/x-tex">E\subseteq[V]^2</annotation></semantics></math> any subset of the set of all two-element subsets of <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mi>V</mi></mrow><annotation encoding="application/x-tex">V</annotation></semantics></math></em>, then a usual meaning of <em>subgraph</em> of <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mo stretchy="false">(</mo><mi>V</mi><mo>,</mo><mi>E</mi><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">(V,E)</annotation></semantics></math> is (cf. e.g. <a href="#DiestelGraphTheoryFourthEd">p. 3</a>): any pair <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mo stretchy="false">(</mo><mi>W</mi><mo>,</mo><mi>F</mi><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">(W,F)</annotation></semantics></math> with <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mi>W</mi><mo>⊆</mo><mi>V</mi></mrow><annotation encoding="application/x-tex">W\subseteq V</annotation></semantics></math>, <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mi>F</mi><mo>⊆</mo><mi>E</mi></mrow><annotation encoding="application/x-tex">F\subseteq E</annotation></semantics></math>, and<sup id="fnref:1"><a href="#fn:1" rel="footnote">1</a></sup> <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mi>F</mi><mo>⊆</mo><mo stretchy="false">[</mo><mi>W</mi><msup><mo stretchy="false">]</mo> <mn>2</mn></msup></mrow><annotation encoding="application/x-tex">F\subseteq [W]^2</annotation></semantics></math>.</p> <p>In particular, such a subgraph <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mo stretchy="false">(</mo><mi>W</mi><mo>,</mo><mi>F</mi><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">(W,F)</annotation></semantics></math> may have isolated vertices which are not isolated in the ambient graph <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mi>G</mi></mrow><annotation encoding="application/x-tex">G</annotation></semantics></math>, and <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mo stretchy="false">(</mo><mi>W</mi><mo>,</mo><mi>F</mi><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">(W,F)</annotation></semantics></math> need not be an <em>induced</em> subgraph, which by definition is a subgraph in the above sense for which <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mi>F</mi><mo>=</mo><mo stretchy="false">[</mo><mi>W</mi><msup><mo stretchy="false">]</mo> <mn>2</mn></msup><mo>∩</mo><mi>E</mi></mrow><annotation encoding="application/x-tex">F = [W]^2\cap E</annotation></semantics></math>. In words: the edge-set of an <em>induced</em> subgraph must contain all edges <em>induced</em> within the ambient graph by the vertex set of the subgraph.<sup id="fnref:2"><a href="#fn:2" rel="footnote">2</a></sup></p> <p>Another usual notion of subgraph in combinatorics is<sup id="fnref:3"><a href="#fn:3" rel="footnote">3</a></sup> <em>spanning</em> subgraph:</p> <p>this means just any subgraph <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mo stretchy="false">(</mo><mi>W</mi><mo>,</mo><mi>F</mi><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">(W,F)</annotation></semantics></math> in the above sense with <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mi>W</mi><mo>=</mo><mi>V</mi></mrow><annotation encoding="application/x-tex">W=V</annotation></semantics></math>. There are three kinds of spanning subgraphs which are the most studied: <span class="newWikiWord">Hamilton circuits<a href="/nlab/new/Hamilton+circuit">?</a></span><sup id="fnref:4"><a href="#fn:4" rel="footnote">4</a></sup>, <span class="newWikiWord">perfect matchings<a href="/nlab/new/perfect+matching">?</a></span> and <span class="newWikiWord">spanning trees<a href="/nlab/new/spanning+tree">?</a></span>.</p> <p>From the <a class="existingWikiWord" href="/nlab/show/nPOV">nPOV</a>, it is often possible to describe notions of subgraph in terms of types of monomorphisms in categories of graphs; for example,</p> <ul> <li> <p><em>subgraphs</em> are <a class="existingWikiWord" href="/nlab/show/monos">monos</a>, and</p> </li> <li> <p><em>induced subgraphs</em> are <a class="existingWikiWord" href="/nlab/show/regular+monos">regular monos</a></p> </li> </ul> <p>in the <a class="existingWikiWord" href="/nlab/show/category+of+simple+graphs">category of simple graphs</a>, and similarly for suitable categories of other types of graph.</p> <p>One synonym, in the nLab<sup id="fnref:5"><a href="#fn:5" rel="footnote">5</a></sup> for <em>induced subgraph</em> is <em>full subgraph</em>, for brevity, and for harmony with other uses of <em>full</em> in category theory (but also for more precise reasons).</p> <p>The precise meaning of <em>subgraph</em> depends on the chosen formalization of <em>graph</em>, needless to say.</p> <h2 id="undirected_graphs_as_1complexes_barycentric_subdivision">Undirected graphs as 1-complexes, barycentric subdivision</h2> <p>Recall that a <a class="existingWikiWord" href="/nlab/show/simplicial+complex">simplicial complex</a> of dimension one consists of the data of a set <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mi>V</mi></mrow><annotation encoding="application/x-tex">V</annotation></semantics></math> together with a set <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mi>S</mi></mrow><annotation encoding="application/x-tex">S</annotation></semantics></math> of non-empty subsets of <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mi>V</mi></mrow><annotation encoding="application/x-tex">V</annotation></semantics></math> of cardinality at most <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mn>2</mn></mrow><annotation encoding="application/x-tex">2</annotation></semantics></math>, that contains all of the <a class="existingWikiWord" href="/nlab/show/singleton">singleton</a> subsets. In other words, a 1-dimensional simplicial complex is essentially the same thing as a simple graph, with the set of edges being determined by the set of simplices and vice versa:</p> <div class="maruku-equation"><math xmlns="http://www.w3.org/1998/Math/MathML" display="block" class="maruku-mathml"><semantics><mrow><mi>E</mi><mo>=</mo><mo stretchy="false">{</mo><mo stretchy="false">{</mo><mi>x</mi><mo>,</mo><mi>y</mi><mo stretchy="false">}</mo><mo lspace="mediummathspace" rspace="mediummathspace">∣</mo><mo stretchy="false">{</mo><mi>x</mi><mo>,</mo><mi>y</mi><mo stretchy="false">}</mo><mo>∈</mo><mi>S</mi><mo>,</mo><mi>x</mi><mo>≠</mo><mi>y</mi><mo stretchy="false">}</mo><mspace width="2em"></mspace><mi>S</mi><mo>=</mo><mo stretchy="false">{</mo><mo stretchy="false">{</mo><mi>x</mi><mo stretchy="false">}</mo><mo lspace="mediummathspace" rspace="mediummathspace">∣</mo><mi>x</mi><mo>∈</mo><mi>V</mi><mo stretchy="false">}</mo><mo>∪</mo><mi>E</mi></mrow><annotation encoding="application/x-tex"> E = \{\{x,y\} \mid \{x,y\} \in S, x \ne y\} \qquad S = \{\{x\} \mid x \in V\} \cup E </annotation></semantics></math></div> <p>For this reason, simple graphs are sometimes referred to as <strong>simplicial graphs</strong> <a href="#GrossTucker">(Gross & Tucker 1987)</a>. On the other hand, an undirected graph <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mi>G</mi></mrow><annotation encoding="application/x-tex">G</annotation></semantics></math> with loops or multiple edges can more generally be seen as a 1-dimensional <a class="existingWikiWord" href="/nlab/show/CW-complex">CW-complex</a> (or more precisely, it has a <a class="existingWikiWord" href="/nlab/show/geometric+realization">geometric realization</a> <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mo stretchy="false">|</mo><mi>G</mi><mo stretchy="false">|</mo></mrow><annotation encoding="application/x-tex">|G|</annotation></semantics></math> as a CW-complex in which 0-cells correspond to vertices and 1-cells to edges).</p> <p>Given a general undirected graph, it is always possible to obtain a simple graph through the process of <em><a class="existingWikiWord" href="/nlab/show/barycentric+subdivision">barycentric subdivision</a></em>. Let <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mi>G</mi></mrow><annotation encoding="application/x-tex">G</annotation></semantics></math> be a graph with vertex set <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mi>V</mi></mrow><annotation encoding="application/x-tex">V</annotation></semantics></math> and edge set <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mi>E</mi></mrow><annotation encoding="application/x-tex">E</annotation></semantics></math>. The <strong>barycentric subdivision</strong> of <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mi>G</mi></mrow><annotation encoding="application/x-tex">G</annotation></semantics></math> is the graph <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mi>G</mi><mo>′</mo></mrow><annotation encoding="application/x-tex">G'</annotation></semantics></math> with vertex set <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mi>V</mi><mo>∪</mo><mi>E</mi></mrow><annotation encoding="application/x-tex">V \cup E</annotation></semantics></math>, and with an edge joining <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mi>v</mi><mo>∈</mo><mi>V</mi></mrow><annotation encoding="application/x-tex">v \in V</annotation></semantics></math> to <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mi>e</mi><mo>∈</mo><mi>E</mi></mrow><annotation encoding="application/x-tex">e \in E</annotation></semantics></math> just in case <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mi>v</mi></mrow><annotation encoding="application/x-tex">v</annotation></semantics></math> is incident to (i.e., at either end of) <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mi>e</mi></mrow><annotation encoding="application/x-tex">e</annotation></semantics></math> in <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mi>G</mi></mrow><annotation encoding="application/x-tex">G</annotation></semantics></math>. It is easy to check that <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mi>G</mi><mo>′</mo></mrow><annotation encoding="application/x-tex">G'</annotation></semantics></math> contains no loops, while the two-fold barycentric subdivision <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mi>G</mi><mo>″</mo></mrow><annotation encoding="application/x-tex">G''</annotation></semantics></math> contains no loops or multiple edges, in other words is a simple graph. (More generally, the <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mi>n</mi></mrow><annotation encoding="application/x-tex">n</annotation></semantics></math>-fold barycentric subdivision contains no circuit of length <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mo>≤</mo><mi>n</mi></mrow><annotation encoding="application/x-tex">\le n</annotation></semantics></math>). Part of the reason for the importance of simple graphs is that many “topological” properties of a graph <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mi>G</mi></mrow><annotation encoding="application/x-tex">G</annotation></semantics></math> (such as <a class="existingWikiWord" href="/nlab/show/planar+graph">planarity</a>, first <a class="existingWikiWord" href="/nlab/show/Betti+number">Betti number</a>, etc., which can be defined in terms of the geometric realization of <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mi>G</mi></mrow><annotation encoding="application/x-tex">G</annotation></semantics></math>) are preserved under barycentric subdivision. (Although obviously, not all <em>graph-theoretic</em> properties are preserved. For example, barycentric subdivision always produces a <a class="existingWikiWord" href="/nlab/show/bipartite+graph">bipartite graph</a>).</p> <h2 id="flavors_of_graphs">Flavors of graphs</h2> <ul> <li> <p><a class="existingWikiWord" href="/nlab/show/reflexive+graph">reflexive graph</a></p> </li> <li> <p><a class="existingWikiWord" href="/nlab/show/directed+graph">directed graph</a></p> </li> </ul> <h2 id="lawveres_remarks_on_graph_theory">Lawvere’s remarks on graph theory</h2> <p>At the <a class="existingWikiWord" href="/nlab/show/Como">Como</a> conference in 1990, <a class="existingWikiWord" href="/nlab/show/William+Lawvere">William Lawvere</a> gave a videotaped lecture including the following remarks:</p> <blockquote> <p id="LawvreOnGraphTheory"> I have great problems reading books on graph theory, books and papers on graph theory, because they never tell you exactly what they are talking about. Sometimes the graphs are [word inaudible, even when played slower], sometimes they are absolutely reflexive, sometimes they are not. Even if they go so far as talking about homomorphisms, I still don’t know exactly what that is, i.e., which category are we in? What they should do is admit that they are working in three or four <em>different</em> categories and they don’t know how to pass from one to the other, and so on, and [inaudible words] to simplify.<br />But no, they prefer to talk in a vague way and smushing these together. [inaudible] tried to understand some of the problems of graph theorists and get [bogged? locked?] in the first page. Does anybody actually know what a graph minor is? [some interjection from the audience] Graph minor. Big problem. (..) you see, this famous [inaudible works] problem on graph minors. Looks like that that might be interesting. But I can’t determine <em>exactly</em> what it is, because, if you read the first parts of the paper, they waffle, you see, they don’t give you a <em>property</em> (…) ([William Lawvere] in his 1990 lecture at <a class="existingWikiWord" href="/nlab/show/Como">Como</a>, Italy, Villa Olmo)</p> </blockquote> <h2 id="in_constructive_mathematics">In constructive mathematics</h2> <p>The notion of graph bifurcates in <a class="existingWikiWord" href="/nlab/show/constructive+mathematics">constructive mathematics</a>:</p> <ul> <li> <p>The set of edges of a graph could be defined with a <a class="existingWikiWord" href="/nlab/show/denial+inequality">denial inequality</a>:</p> <div class="maruku-equation"><math xmlns="http://www.w3.org/1998/Math/MathML" display="block" class="maruku-mathml"><semantics><mrow><mi>E</mi><mo>≔</mo><mo stretchy="false">{</mo><mo stretchy="false">(</mo><mi>x</mi><mo>,</mo><mi>y</mi><mo stretchy="false">)</mo><mo>∈</mo><mi>V</mi><mo>×</mo><mi>V</mi><mo stretchy="false">|</mo><mi>x</mi><mo>≠</mo><mi>y</mi><mo stretchy="false">}</mo></mrow><annotation encoding="application/x-tex">E \coloneqq \{(x, y) \in V \times V \vert x \neq y\}</annotation></semantics></math></div></li> <li> <p>The set of edges of a graph could be defined with a <a class="existingWikiWord" href="/nlab/show/tight+apartness+relation">tight apartness relation</a>:</p> <div class="maruku-equation"><math xmlns="http://www.w3.org/1998/Math/MathML" display="block" class="maruku-mathml"><semantics><mrow><mi>E</mi><mo>≔</mo><mo stretchy="false">{</mo><mo stretchy="false">(</mo><mi>x</mi><mo>,</mo><mi>y</mi><mo stretchy="false">)</mo><mo>∈</mo><mi>V</mi><mo>×</mo><mi>V</mi><mo stretchy="false">|</mo><mi>x</mi><mo>#</mo><mi>y</mi><mo stretchy="false">}</mo></mrow><annotation encoding="application/x-tex">E \coloneqq \{(x, y) \in V \times V \vert x \# y\}</annotation></semantics></math></div></li> </ul> <h2 id="related_concepts">Related concepts</h2> <ul> <li> <p><a class="existingWikiWord" href="/nlab/show/omega-graph">omega-graph</a></p> </li> <li> <p><a class="existingWikiWord" href="/nlab/show/planar+graph">planar graph</a>, <a class="existingWikiWord" href="/nlab/show/connected+graph">connected graph</a></p> </li> <li> <p><a class="existingWikiWord" href="/nlab/show/acyclic+graph">acyclic graph</a></p> </li> <li> <p><a class="existingWikiWord" href="/nlab/show/signed+graph">signed graph</a></p> </li> <li> <p><a class="existingWikiWord" href="/nlab/show/empty+graph">empty graph</a></p> </li> <li> <p><a class="existingWikiWord" href="/nlab/show/ribbon+graph">ribbon graph</a></p> </li> <li> <p><a class="existingWikiWord" href="/nlab/show/hypergraph">hypergraph</a></p> </li> <li> <p><a class="existingWikiWord" href="/nlab/show/quiver">quiver</a>, <a class="existingWikiWord" href="/nlab/show/McKay+quiver">McKay quiver</a></p> </li> <li> <p><a class="existingWikiWord" href="/nlab/show/n-quiver">n-quiver</a></p> </li> <li> <p><a class="existingWikiWord" href="/nlab/show/distance+%28graph+theory%29">distance (graph theory)</a></p> </li> <li> <p><a class="existingWikiWord" href="/nlab/show/relation">relation</a></p> </li> <li> <p><a class="existingWikiWord" href="/nlab/show/category">category</a>, <a class="existingWikiWord" href="/nlab/show/free+category">free category</a></p> </li> <li> <p><a class="existingWikiWord" href="/nlab/show/Feynman+diagram">Feynman diagram</a></p> </li> <li> <p><a class="existingWikiWord" href="/nlab/show/graph+complex">graph complex</a>, <a class="existingWikiWord" href="/nlab/show/formality+of+the+little+n-disk+operad">formality of the little n-disk operad</a></p> </li> <li> <p><a class="existingWikiWord" href="/nlab/show/graph+of+groups">graph of groups</a></p> </li> <li> <p><a class="existingWikiWord" href="/nlab/show/semi-graph">semi-graph</a></p> </li> <li> <p><a class="existingWikiWord" href="/nlab/show/loop+graph+object">loop graph object</a></p> </li> </ul> <h2 id="references">References</h2> <p>Textbooks:</p> <ul> <li> <p>Frank Harary (1969), <em>Graph Theory</em>, Addison-Wesley.</p> </li> <li> <p>Frank Harary and E.M. Palmer (1973), <em>Graphical Enumeration</em>, Academic Press.</p> </li> <li id="Serre1977"> <p><a class="existingWikiWord" href="/nlab/show/Jean-Pierre+Serre">Jean-Pierre Serre</a> (1977), <em>Trees</em>, Springer.</p> </li> <li> <p><a class="existingWikiWord" href="/nlab/show/W.+T.+Tutte">W. T. Tutte</a> (1984), <em>Graph Theory</em>, Addison-Wesley.</p> </li> <li id="GrossTucker"> <p>Jonathan L. Gross and Thomas W. Tucker (1987), <em>Topological Graph Theory</em>, Wiley.</p> </li> <li> <p>Gunther Schmidt and Thomas Ströhlein (1993), <em>Relations and Graphs: Discrete Mathematics for Computer Scientists</em>, EATCS Monographs on Theoretical Computer Science, Springer.</p> </li> <li id="HandbookOfCombinatoricsVol1"> <p>A. Bondy. Basic Graph Theory: Paths and Circuits. Elsevier Amsterdam, 1995, Vol. 1, pp. 1–110</p> </li> <li> <p>Chris Godsil and Gordon Royle (2001), <em>Algebraic Graph Theory</em>, Springer.</p> </li> <li id="DiestelGraphTheoryFourthEd"> <p><a class="existingWikiWord" href="/nlab/show/Reinhard+Diestel">Reinhard Diestel</a>, <em>Graph Theory</em>, Graduate Texts in Mathematics <strong>173</strong> 5th edition (2017) [<a href="https://diestel-graph-theory.com/">website</a>, <a href="https://doi.org/10.1007/978-3-662-53622-3">doi:10.1007/978-3-662-53622-3</a>]</p> </li> <li> <p>Teo Banica. <em>Graphs and their symmetries</em> (2024). (<a href="https://arxiv.org/abs/2406.03664">arXiv:2406.03664</a>).</p> </li> </ul> <p>Other references:</p> <ul> <li id="Law89"> <p><a class="existingWikiWord" href="/nlab/show/Bill+Lawvere">Bill Lawvere</a> (1989), <em>Qualitative distinctions between some toposes of generalized graphs</em>, in Categories in computer science and logic (Boulder, CO, 1987), volume 92 of <em>Contemporary Mathematics</em>, 261–299. American Mathematical Society, Providence, RI.</p> </li> <li> <p>E. Babson, H. Barcelo, M. de Longueville, R. Laubenbacher, A Homotopy Theory for Graphs, <a href="http://arxiv.org/abs/math/0403146">arXiv:math/0403146</a></p> </li> <li> <p><a class="existingWikiWord" href="/nlab/show/Ronnie+Brown">Ronnie Brown</a>, I. Morris, J. Shrimpton, and C.D. Wensley (2008), <em>Graphs of Morphisms of Graphs</em>, Electronic Journal of Combinatorics, A1 of Volume 15(1), 1–28.</p> </li> <li id="Harary1953"> <p><span class="newWikiWord">Frank Harary<a href="/nlab/new/Frank+Harary">?</a></span>: <em>On the notion of balance of a signed graph</em>. The Michigan Mathemathical Journal, Volume 2, Issue 2 (1953), 143-146.</p> </li> <li id="JoyalKockQPL"> <p><a class="existingWikiWord" href="/nlab/show/Andr%C3%A9+Joyal">André Joyal</a> and <a class="existingWikiWord" href="/nlab/show/Joachim+Kock">Joachim Kock</a>, Feynman graphs, and nerve theorem for compact symmetric multicategories (extended abstract), in <em>Proceedings of the 6th International Workshop on Quantum Physics and Logic</em>(Oxford 2009), Electronic Notes in Theoretical Computer Science 270 (2) (2011), 105-113. <a href="https://arxiv.org/abs/0908.2675">arXiv:0908.2675</a></p> </li> <li id="Kock2016GHP"> <p><a class="existingWikiWord" href="/nlab/show/Joachim+Kock">Joachim Kock</a>, Graphs, hypergraphs, and properads, <em>Collect. Math.</em> 67 (2016), 155-190. <a href="https://arxiv.org/abs/1407.3744">arXiv:1407.3744</a></p> </li> <li id="Kock2016BM"> <p><a class="existingWikiWord" href="/nlab/show/Joachim+Kock">Joachim Kock</a>, Cospan construction of the graph category of Borisov and Manin, <a href="https://arxiv.org/abs/1611.10342">arXiv:1611.10342</a></p> </li> <li> <p>Martin Schmidt, <em>Functorial Approach to Graph and Hypergraph Theory</em>, (<a href="https://arxiv.org/abs/1907.02574">arXiv:1907.02574</a>)</p> </li> <li id="Vigna97"> <p>Sebastiano Vigna, <em>A guided tour in the topos of graphs</em>, 1997. (<a href="https://arxiv.org/abs/math/0306394">arXiv:0306394</a>)</p> </li> </ul> <p>See also <a class="existingWikiWord" href="/nlab/show/quiver#references">quiver - references</a>.</p> <p>Discussion of use of <a class="existingWikiWord" href="/nlab/show/simplicial+complexes">simplicial complexes</a> in graph theory:</p> <ul> <li>MO, <em><a href="http://mathoverflow.net/questions/161586/what-have-simplicial-complexes-ever-done-for-graph-theory">What have simplicial complexes ever done for graph theory?</a></em></li> </ul> <div class="footnotes"><hr /><ol><li id="fn:1"> <p>The last condition is to ensure that <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mo stretchy="false">(</mo><mi>W</mi><mo>,</mo><mi>F</mi><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">(W,F)</annotation></semantics></math> is itself again a graph, which would not be guaranteed if we defined subgraph to be just any pair of subsets of the respective sets <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mi>V</mi></mrow><annotation encoding="application/x-tex">V</annotation></semantics></math> and <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline" class="maruku-mathml"><semantics><mrow><mi>E</mi></mrow><annotation encoding="application/x-tex">E</annotation></semantics></math>. <a href="#fnref:1" rev="footnote">↩</a></p> </li><li id="fn:2"> <p>This happens to be the usual notion of substructure in model theory, for any relational structure. <a href="#fnref:2" rev="footnote">↩</a></p> </li><li id="fn:3"> <p>Somewhat counterintuitively (with regard to connotations of the words <em>spanning</em> and <em>induced</em>), a <em>spanning</em> subgraph need not be <em>induced</em>, and in fact it never is, <em>except</em> if the subgraph is the graph itself. <a href="#fnref:3" rev="footnote">↩</a></p> </li><li id="fn:4"> <p>We here follow A. Bondy’s choice of words in <a href="#HandbookOfCombinatoricsVol1">p. 20</a>, both in the decision whether to use <em>hamiltonian</em> or <em>Hamilton</em>, and whether to use <em>cycle</em> or <em>circuit</em>. The term <em>circuit</em> is less usual than <em>cycle</em> in combinatorics, but less ambiguous, not longer, and more clearly signalling that the combinatorial notion is meant (not one of the many other meanings of <em>cycle</em>). One argument in favor of <em>Hamilton</em> is that <em>any</em> circuit, by itself, is <em>hamiltonian</em>. <a href="#fnref:4" rev="footnote">↩</a></p> </li><li id="fn:5"> <p>Incidentally, the term <em>full</em> was in use in mid-twentieth century graph theory, then seems to have fallen out of favor. <a href="#fnref:5" rev="footnote">↩</a></p> </li></ol></div></body></html> </div> <div class="revisedby"> <p> Last revised on November 19, 2024 at 12:14:23. See the <a href="/nlab/history/graph" style="color: #005c19">history</a> of this page for a list of all contributions to it. </p> </div> <div class="navigation navfoot"> <a href="/nlab/edit/graph" accesskey="E" class="navlink" id="edit" rel="nofollow">Edit</a><a href="https://nforum.ncatlab.org/discussion/3726/#Item_24">Discuss</a><span class="backintime"><a href="/nlab/revision/graph/108" accesskey="B" class="navlinkbackintime" id="to_previous_revision" rel="nofollow">Previous revision</a></span><a href="/nlab/show/diff/graph" accesskey="C" class="navlink" id="see_changes" rel="nofollow">Changes from previous revision</a><a href="/nlab/history/graph" accesskey="S" class="navlink" id="history" rel="nofollow">History (108 revisions)</a> <a href="/nlab/show/graph/cite" style="color: black">Cite</a> <a href="/nlab/print/graph" accesskey="p" id="view_print" rel="nofollow">Print</a> <a href="/nlab/source/graph" id="view_source" rel="nofollow">Source</a> </div> </div>  </div>  </body> </html>