nLab
graph

Idea

A graph is a collection of vertices and edges; each edge links a pair of vertices. 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:A\to B$ as a subobject of the product $A\times B$, is unrelated; see graph of a function for more on this.

Definitions

Let $V$ and $E$ be sets; call an element of $V$ a vertex and an element of $E$ an edge. A graph is given by $V$, $E$, and a mapping $d$ 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^2$ is the cartesian product of $V$ with itself, the set of ordered pairs $(x,y)$ of vertices;
• ${\Delta }_V$ is the diagonal subset of $V$, the set of pairs $(x,x)$, so that its complement $V^2\setminus {\Delta }_V$ is the set of pairs as above where $x\ne y$;
• $⟨\genfrac{}{}{0ex}{}{V}{2}⟩$ is the quotient set of $V^2$ in which $(x,y)$ is identified with $(y,x)$, the set of unordered pairs $\{x,y\}$ of vertices;
• $\left(\genfrac{}{}{0ex}{}{V}{2}\right)$ is the quotient set of $V^2\setminus {\Delta }_V$ in which $(x,y)$ is identified with $(y,x)$, the set of unordered pairs where $x\ne y$.

We are now ready for the first batch of definitions.

• For a simple graph, a pair of vertices is a subset of $V$ of cardinality $2$, and we interpret edges as unordered pairs of vertices in a one-to-one way. Thus a simple graph is given by $V$, $E$, and an injective function $d:E\hookrightarrow \left(\genfrac{}{}{0ex}{}{V}{2}\right)$. Among graph theorists, this is the standard 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 $V$, $E$, and an arbitrary function $d:E\to \left(\genfrac{}{}{0ex}{}{V}{2}\right)$.

• For a loop graph, a pair of vertices is any subset of the form $\{x,y\}$, where $x=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 $V$, $E$, and an injective function $d:E\hookrightarrow ⟨\genfrac{}{}{0ex}{}{V}{2}⟩$.

• 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 $V$, $E$, and a function $d:E\to ⟨\genfrac{}{}{0ex}{}{V}{2}⟩$.

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.

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 $V$, $E$, and an injective function $d:E\hookrightarrow V^2\setminus {\Delta }_V$;
• a directed multigraph consists of $V$, $E$, and a function $d:E\to V^2\setminus {\Delta }_V$;
• a directed loop graph consists of $V$, $E$, and an injective function $d:E\hookrightarrow V^2$;
• a directed pseudograph consists of $V$, $E$, and a function $d: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 $x$ to $y$ if and only if there is an edge from $y$ to $x$, or some mixture of these.

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 $e$ with $d(e)=(x,y)$ is an arc from $x$ to $y$, while a line $e$ such that $d(e)=\{x,y\}$ is a line between $x$ and $y$. 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 $V$; say that $x$ and $y$ are adjacent, written $x\sim y$, if there exists an edge $e$ such that $d(e)=(x,y)$ or $d(e)=\{x,y\}$. A directed loop graph is determined entirely by this relation; we may say that it is $V$ equipped with a binary relation. Then a simple directed graph is $V$ equipped with an irreflexive relation (or equivalently a reflexive relation), and an undirected loop graph is $V$ equipped with a symmetric relation.

A graph is finite if $V$ and $E$ 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)$th entry gives the number of edges $e$ between the $i$th and $j$th vertices or from the $i$th vertex to the $j$th vertex. In the examples above where a graph is determined by a binary relation on $V$, then matrix multiplication gives composition of relations.

Morphisms of graphs

An isomorphism from $G=(V,E,d)$ to $G\prime =(V\prime ,E\prime ,d\prime )$ consists of a bijection $f:V\to V\prime$, together with a bijection from $E$ to $E\prime$ (also denoted $f$) such that $f$ commutes with $d$; that is, $d(f(e))=(f(x),f(y))$ or $d(f(e))=\{f(x),f(y)\}$ whenever $d(e)=(x,y)$ or $d(e)=\{x,y\}$ (as appropriate). Two graphs $G$ and $G\prime$ are isomorphic if there exists such an isomorphism. Then finite graphs $G$ and $G\prime$ 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 $G$ to $G\prime$ should consist of functions $f:V\to V\prime$ and $f:E\to E\prime$ such that $f$ commutes with $d$. However, some authors allow $f(e)$ to be undefined if $d(e)=(x,y)$ or $d(e)=\{x,y\}$ but $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 $\le$ 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.).

Flavors of graphs

• reflexive graph

• directed graph

Related concepts

• graph

  • omega-graph

• ribbon graph

• hypergraph

• quiver

  • n-quiver

• relation

• category, free category

References

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

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

• Joachim Lambek and Philip Scott (1986), Introduction to Higher Order Categorical Logic, Cambridge University Press.

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

• 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