nLab graph

Contents

This page is about the notion in combinatorics. For other notions of the same name see at graph of a function and graph of a functor.


Contents

Idea

A graph is a collection of vertices and edges; each edge links a pair of vertices, defining a relationship of incidence between vertices and edges. There are several variations on the idea, described below.

This is the sense of graph in combinatorics; the other sense in high-school algebra, which interprets a morphism f:ABf: A \to B as a subobject of the product A×BA \times B, is unrelated; see graph of a function for more on this.

Definitions

Let VV and EE be sets; call an element of VV a vertex and an element of EE an edge. A graph is given by VV, EE, and a mapping dd 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:

  • V 2V^2 is the cartesian product of VV with itself, the set of ordered pairs (x,y)(x,y) of vertices;
  • Δ V\Delta_V is the diagonal subset of VV, the set of pairs (x,x)(x,x), so that its complement V 2Δ VV^2 \setminus \Delta_V is the set of pairs as above where xyx \neq y;
  • V2\left\langle{V \atop 2}\right\rangle is the quotient set of V 2V^2 in which (x,y)(x,y) is identified with (y,x)(y,x), the set of unordered pairs {x,y}\{x,y\} of vertices;
  • (V2)\left({V \atop 2}\right) is the quotient set of V 2Δ VV^2 \setminus \Delta_V in which (x,y)(x,y) is identified with (y,x)(y,x), the set of unordered pairs where xyx \neq y.

Undirected graphs

We are now ready for the first batch of definitions.

  • For a simple graph, a pair of vertices is a subset of VV of cardinality 22, and we interpret edges as unordered pairs of vertices in a one-to-one way. Thus a simple graph is given by VV, EE, and an injective function d:E(V2)d: E \hookrightarrow \left({V \atop 2}\right). Among graph theorists, this is often the default meaning of ‘graph’ unless another is specified. The category of simple graphs is called SimpGph

  • For a multigraph, 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 VV, EE, and an arbitrary function d:E(V2)d: E \to \left({V \atop 2}\right).

  • For a loop graph, a pair of vertices is any subset of the form {x,y}\{x,y\}, where x=yx = y is allowed, and we interpret edges as pairs of vertices in a one-to-one way again. Thus a loop-graph is given by VV, EE, and an injective function d:EV2d: E \hookrightarrow \left\langle{V \atop 2}\right\rangle.

  • For a pseudograph, 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 VV, EE, and a function d:EV2d: E \to \left\langle{V \atop 2}\right\rangle.

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. p. 142) 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).

Directed graphs

In all four of the above, edges are interpreted as unordered pairs. If we instead interpret edges as ordered pairs, then we get four new concepts:

  • A directed graph consists of VV, EE, and an injective function d:EV 2Δ Vd: E \hookrightarrow V^2 \setminus \Delta_V;
  • a directed multigraph consists of VV, EE, and a function d:EV 2Δ Vd: E \to V^2 \setminus \Delta_V;
  • a directed loop graph consists of VV, EE, and an injective function d:EV 2d: E \hookrightarrow V^2;
  • a directed pseudograph consists of VV, EE, and a function d:EV 2d: E \to V^2.

Directed pseudographs are commonly used in category theory, where they are often called ‘directed graphs’, ‘digraphs’, or (less ambiguously) ‘quivers’.

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.

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 xx to yy if and only if there is an edge from yy to xx, or some mixture of these.

Undirected graphs as directed graphs with an involution

There is an alternative definition of an undirected graph allowing loops and multiple edges (cf. Serre 1977), that begins with the structure of a quiver s,t:EVs,t : E \rightrightarrows V and then asks in addition for a fixed point free involution on edges i:EEi : E \to E swapping source and target, i.e., such that

i(i(e))=ei(e)es(i(e))=t(e)t(i(e))=s(e) i(i(e)) = e \quad i(e) \ne e \quad s(i(e)) = t(e) \quad t(i(e)) = s(e)

Of course, since the source s:EVs : E \to V and target t:EVt : E \to V functions determine each other in the presence of the involution i:EEi : E \to E, it is enough to give, say, ss and ii to define an undirected graph. In that case, one might alternatively view EE as a set of “half-edges” or “flags” (with ii the involution swapping the two halves of an edge), and even lift the condition that ii 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).

Although this definition of undirected graphs with open edges is standard (cf. ribbon graph), Kock (2016b) 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 Joyal and Kock (2009): they define a “Feynman graph” as a triple of finite sets V,E,HV, E, H together with a triple of a function t:HVt : H \to V, an injection s:HEs : H \to E, and a fixed point free involution i:EEi : E \to E. (See also Kock (2016a) for further discussion.)

Orientations

An orientation of an undirected graph is the choice of a direction for every edge. Formally, if we define undirected graphs as above to be quivers EVE \rightrightarrows V equipped with a fixed point free involution i:EEi : E \to E, then an orientation corresponds to the choice of a subset E +EE^+ \subseteq E such that EE is the disjoint union E=E +i(E +)E = E^+ \uplus i(E^+).

Any orientation of an undirected graph induces a corresponding directed graph E +VE^+ \rightrightarrows V. In many situations, though, it is useful to consider a given undirected graph equipped with one of many possible orientations. For example, various graph invariants? (such as the flow polynomial?, or Tutte‘s original definition of the Tutte polynomial?) can be defined for an arbitrary orientation of a graph, but are independent of the choice of orientation.

Auxiliary definitions

The term arc is often used for an ordered edge, while line is sometimes used for an unordered edge. We say that an arc ee with d(e)=(x,y)d(e) = (x,y) is an arc from xx to yy, while a line ee such that d(e)={x,y}d(e) = \{x,y\} is a line between xx and yy. In either case, a loop is an edge from a vertex to itself or between a vertex and itself; only (possibly directed) loop graphs and pseudographs can have loops.

Given any sort of graph, we can define a binary relation on VV; say that xx and yy are adjacent, written xyx \sim y, if there exists an edge ee such that d(e)=(x,y)d(e) = (x,y) or d(e)={x,y}d(e) = \{x,y\}. A directed loop graph is determined entirely by this relation; we may say that it is VV equipped with a binary relation. Then a simple directed graph is VV equipped with an irreflexive relation (or equivalently a reflexive relation), and an undirected loop graph is VV equipped with a symmetric relation.

A graph is finite if VV and EE are both finite sets. Given a linear ordering of the vertices of a finite graph, its adjacency matrix is a square matrix whose (i,j)(i,j)th entry gives the number of edges ee between the iith and jjth vertices or from the iith vertex to the jjth vertex. In the examples above where a graph is determined by a binary relation on VV, then matrix multiplication gives composition of relations.

Morphisms of graphs

An isomorphism from G=(V,E,d)G = (V,E,d) to G=(V,E,d)G' = (V',E',d') consists of a bijection f:VVf: V \to V', together with a bijection from EE to EE' (also denoted ff) such that ff commutes with dd; that is, d(f(e))=(f(x),f(y))d(f(e)) = (f(x),f(y)) or d(f(e))={f(x),f(y)}d(f(e)) = \{f(x),f(y)\} whenever d(e)=(x,y)d(e) = (x,y) or d(e)={x,y}d(e) = \{x,y\} (as appropriate). Two graphs GG and GG' are isomorphic if there exists such an isomorphism. Then finite graphs GG and GG' 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.

A morphism from GG to GG' should consist of functions f:VVf: V \to V' and f:EEf: E \to E' such that ff commutes with dd. However, some authors allow f(e)f(e) to be undefined if d(e)=(x,y)d(e) = (x,y) or d(e)={x,y}d(e) = \{x,y\} but f(x)=f(y)f(x) = f(y) 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.

Under the second notion of morphism (where simple graphs are identified with sets equipped with a symmetric reflexive relation), the category of simple graphs has many desirable properties (q.v.).

Notions of subgraphs from the nPOV

A usual definition of subgraph in combinatorics is, roughly: subset. More precisely, if undirected simple graph means pair (V,E)(V,E) of two sets, with E[V] 2E\subseteq[V]^2 any subset of the set of all two-element subsets of VV, then a usual meaning of subgraph of (V,E)(V,E) is (cf. e.g. p. 3): any pair (W,F)(W,F) with WVW\subseteq V, FEF\subseteq E, and1 F[W] 2F\subseteq [W]^2.

In particular, such a subgraph (W,F)(W,F) may have isolated vertices which are not isolated in the ambient graph GG, and (W,F)(W,F) need not be an induced subgraph, which by definition is a subgraph in the above sense for which F=[W] 2EF = [W]^2\cap E. In words: the edge-set of an induced subgraph must contain all edges induced within the ambient graph by the vertex set of the subgraph.2

Another usual notion of subgraph in combinatorics is3 spanning subgraph:

this means just any subgraph (W,F)(W,F) in the above sense with W=VW=V. There are three kinds of spanning subgraphs which are the most studied: Hamilton circuits?4, perfect matchings? and spanning trees?.

From the nPOV, it is often possible to describe notions of subgraph in terms of types of monomorphisms in categories of graphs; for example,

in the category of simple graphs, and similarly for suitable categories of other types of graph.

One synonym, in the nLab5 for induced subgraph is full subgraph, for brevity, and for harmony with other uses of full in category theory (but also for more precise reasons).

The precise meaning of subgraph depends on the chosen formalization of graph, needless to say.

Undirected graphs as 1-complexes, barycentric subdivision

Recall that a simplicial complex of dimension one consists of the data of a set VV together with a set SS of non-empty subsets of VV of cardinality at most 22, that contains all of the singleton 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:

E={{x,y}{x,y}S,xy}S={{x}xV}E E = \{\{x,y\} \mid \{x,y\} \in S, x \ne y\} \qquad S = \{\{x\} \mid x \in V\} \cup E

For this reason, simple graphs are sometimes referred to as simplicial graphs (Gross & Tucker 1987). On the other hand, an undirected graph GG with loops or multiple edges can more generally be seen as a 1-dimensional CW-complex (or more precisely, it has a geometric realization |G||G| as a CW-complex in which 0-cells correspond to vertices and 1-cells to edges).

Given a general undirected graph, it is always possible to obtain a simple graph through the process of barycentric subdivision. Let GG be a graph with vertex set VV and edge set EE. The barycentric subdivision of GG is the graph GG' with vertex set VEV \cup E, and with an edge joining vVv \in V to eEe \in E just in case vv is incident to (i.e., at either end of) ee in GG. It is easy to check that GG' contains no loops, while the two-fold barycentric subdivision GG'' contains no loops or multiple edges, in other words is a simple graph. (More generally, the nn-fold barycentric subdivision contains no circuit of length n\le n). Part of the reason for the importance of simple graphs is that many “topological” properties of a graph GG (such as planarity, first Betti number, etc., which can be defined in terms of the geometric realization of GG) are preserved under barycentric subdivision. (Although obviously, not all graph-theoretic properties are preserved. For example, barycentric subdivision always produces a bipartite graph).

Flavors of graphs

Lawvere’s remarks on graph theory

At the Como conference in 1990, William Lawvere gave a videotaped lecture including the following remarks:

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 different categories and they don’t know how to pass from one to the other, and so on, and [inaudible words] to simplify.
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 exactly what it is, because, if you read the first parts of the paper, they waffle, you see, they don’t give you a property (…) ([William Lawvere] in his 1990 lecture at Como, Italy, Villa Olmo)

In constructive mathematics

The notion of graph bifurcates in constructive mathematics:

  • The set of edges of a graph could be defined with a denial inequality:

    E{(x,y)V×V|xy}E \coloneqq \{(x, y) \in V \times V \vert x \neq y\}
  • The set of edges of a graph could be defined with a tight apartness relation:

    E{(x,y)V×V|x#y}E \coloneqq \{(x, y) \in V \times V \vert x \# y\}

References

Textbooks:

  • Frank Harary (1969), Graph Theory, Addison-Wesley.

  • Frank Harary and E.M. Palmer (1973), Graphical Enumeration, Academic Press.

  • Jean-Pierre Serre (1977), Trees, Springer.

  • W. T. Tutte (1984), Graph Theory, Addison-Wesley.

  • Jonathan L. Gross and Thomas W. Tucker (1987), Topological Graph Theory, Wiley.

  • Gunther Schmidt and Thomas Ströhlein (1993), Relations and Graphs: Discrete Mathematics for Computer Scientists, EATCS Monographs on Theoretical Computer Science, Springer.

  • A. Bondy. Basic Graph Theory: Paths and Circuits. Elsevier Amsterdam, 1995, Vol. 1, pp. 1–110

  • Chris Godsil and Gordon Royle (2001), Algebraic Graph Theory, Springer.

  • Reinhard Diestel, Graph Theory, Graduate Texts in Mathematics 173 5th edition (2017) [website, doi:10.1007/978-3-662-53622-3]

Other references:

  • Bill Lawvere (1989), Qualitative distinctions between some toposes of generalized graphs, in Categories in computer science and logic (Boulder, CO, 1987), volume 92 of Contemporary Mathematics, 261–299. American Mathematical Society, Providence, RI.

  • E. Babson, H. Barcelo, M. de Longueville, R. Laubenbacher, A Homotopy Theory for Graphs, arXiv:math/0403146

  • Ronnie Brown, I. Morris, J. Shrimpton, and C.D. Wensley (2008), Graphs of Morphisms of Graphs, Electronic Journal of Combinatorics, A1 of Volume 15(1), 1–28.

  • Frank Harary?: On the notion of balance of a signed graph. The Michigan Mathemathical Journal, Volume 2, Issue 2 (1953), 143-146.

  • André Joyal and Joachim Kock, Feynman graphs, and nerve theorem for compact symmetric multicategories (extended abstract), in Proceedings of the 6th International Workshop on Quantum Physics and Logic(Oxford 2009), Electronic Notes in Theoretical Computer Science 270 (2) (2011), 105-113. arXiv:0908.2675

  • Joachim Kock, Graphs, hypergraphs, and properads, Collect. Math. 67 (2016), 155-190. arXiv:1407.3744

  • Joachim Kock, Cospan construction of the graph category of Borisov and Manin, arXiv:1611.10342

  • Martin Schmidt, Functorial Approach to Graph and Hypergraph Theory, (arXiv:1907.02574)

See also quiver - references.

Discussion of use of simplicial complexes in graph theory:


  1. The last condition is to ensure that (W,F)(W,F) 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 VV and EE.

  2. This happens to be the usual notion of substructure in model theory, for any relational structure.

  3. Somewhat counterintuitively (with regard to connotations of the words spanning and induced), a spanning subgraph need not be induced, and in fact it never is, except if the subgraph is the graph itself.

  4. We here follow A. Bondy’s choice of words in p. 20, both in the decision whether to use hamiltonian or Hamilton, and whether to use cycle or circuit. The term circuit is less usual than cycle 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 cycle). One argument in favor of Hamilton is that any circuit, by itself, is hamiltonian.

  5. Incidentally, the term full was in use in mid-twentieth century graph theory, then seems to have fallen out of favor.

Last revised on February 12, 2024 at 04:16:58. See the history of this page for a list of all contributions to it.