nLab
graph

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.

  • 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.

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”, with ii the involution swapping the two halves of an edge. (This point-of-view is often taken, for example, in studies of ribbon graphs and dessins d'enfants.) One can also lift the condition that ii has no fixed points to allow for the possibility of undirected graphs with “dangling” edges (with only one side attached to a vertex).

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.

Mike Shulman: Isn’t there something backwards about defining “isomorphic” and then “isomorphism” and then “morphism”? Doesn’t the logic generally flow in the other direction (especially around here)?

David Roberts: well at least there’s a historical precedent: this is how Bourbaki would have done it via structures :)

Toby: That, and it's simpler to state the definition of ‘isomorphic’ than ‘isomorphism’. Not to mention that graph theorists, in my experience, tend to care much more about the property of being isomorphic than the structure of having an isomorphism. As for ‘morphism’, there's even disagreement about what that should be; I think that my definition is the obvious correct one, but it disagrees with the one at, for example, Wikipedia (although they had my definition in the past); both versions give the same notion of isomorphism, however.

Mike Shulman: Well, but we aren’t graph theorists here, are we? Isn’t it okay for us to rephrase their definitions in the more categorically sensible order?

Toby: I disagree that ‘morphism’ before ‘isomorphism’ is more categorially sensible. That's like defining \leq before ==; sometimes useful, sometimes not. Since I am getting ambiguity about morphisms in what I find online, I'd prefer to do isomorphisms first. With luck, I'll find some terminology to distinguish the two kinds of morphisms, or we can make up our own.

Mike Shulman: Okay, I’ll accept that sometimes it makes sense to have isomorphisms before morphisms. Certainly there are other situations in which the notion of isomorphism is more obvious, or less subject to debate, than the notion of morphism. But I am happy that now “isomorphism” comes before “isomorphic.”

RonnieBrown: I hope it is helpful to add the reference below, which also contains quite a few references to categorical treatments of graphs.

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 circuit?s4, perfect matching?s and spanning tree?s.

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

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.

  • R. Diestel, Graph Theory, 4. ed., Springer 2010

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.

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.

Revised on July 20, 2017 10:37:32 by Noam Zeilberger (194.199.3.13)