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.
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.
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:
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({V \atop 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({V \atop 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 \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 $V$, $E$, and a function $d: 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.
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:
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.
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.
An isomorphism from $G = (V,E,d)$ to $G' = (V',E',d')$ consists of a bijection $f: V \to V'$, together with a bijection from $E$ to $E'$ (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'$ are isomorphic if there exists such an isomorphism. Then finite graphs $G$ and $G'$ 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'$ should consist of functions $f: V \to V'$ and $f: E \to E'$ 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 $\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.).
There is an equivalent definition of pseudograph in the above sense (i.e., of an undirected graph allowing loops and multiple edges), which replaces the set of edges by a set of half-edges. In this formulation (which appears, for example, in the study of ribbon graphs and combinatorial maps), a graph is defined as a pair of sets $V$ and $H$ together with a function $s : H \to V$ and a fixed point free involution $i : H \to H$. An equivalent but more symmetrical formulation (given in Chapter 2.1 of Serre 1977) uses a pair of source and target functions $(s,t) : H \to V\times V$ together with a fixed point free involution $i : H \to H$ such that $s\circ i = t$ (and hence $s = t \circ i$). Here, the set $H$ can also be seen as a set of directed edges. In other words, a pseudograph is just a quiver equipped with a fixed point free involution on directed edges which exchanges source and target. Note an analogy between this way of defining a pseudograph and the definition of a dagger category as a category equipped with a contravariant involution on morphisms.
Given a (pseudo)graph $G$ represented by $(V,H,s,i)$, the edges of $G$ are just the orbits of $i$, which (since $i$ is a fixed point free involution) must all be of length 2, corresponding to pairs of half-edges. Lifting the condition that $i$ has no fixed points also allows to represent graphs with “dangling” edges.
graph
Frank Harary (1969), Graph Theory, Addison-Wesley.
Frank Harary and E.M. Palmer (1973), Graphical Enumeration, Academic Press.
Jean-Pierre Serre (1977), Trees, Springer.
Joachim Lambek and Philip Scott (1986), Introduction to Higher Order Categorical Logic, Cambridge University Press.
Gunther Schmidt and Thomas Ströhlein (1993), Relations and Graphs: Discrete Mathematics for Computer Scientists, EATCS Monographs on Theoretical Computer Science, Springer.
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
Discussion of use of simplicial complexes in graph theory: