The definition of a graph, 2

A few years ago, three consecutive speakers in the pure maths seminar at Queen Mary gave three entirely different definitions of a graph. The next speaker to appear was talking on a topic completely unconnected with graphs, but someone in the audience couldn’t resist asking for his definition of a graph.

There are many definitions of a graph, which are easily seen to be equivalent; but there are also some unexpected byways. Part of the difficulty is that we have to cope with several different kinds of graphs: multiple edges may be allowed or forbidden, loops may be allowed or forbidden, and edges may be undirected or directed. Also, just around the next bend, there are hypergraphs.

So here are a few definitions, all of which are in common use, with indications of how to modify them to take account of the different kinds of graph.

1. A graph consists of a set V of vertices, with an irreflexive and symmetric binary relation called adjacency on V. To allow loops, remove the word “irreflexive”; to allow directed edges, remove the word “symmetric”. Multiple edges require a reformulation where “relation” is replaced by “multirelation”, a multiset of ordered pairs.
2. A graph consists of a set V of vertices, with a set E of unordered pairs (2-element subsets) of V called edges. To allow loops, replace “2-element sets” by “1- or 2-element sets”; to allow directed edges, replace “unordered pairs” by “ordered pairs”. To allow multiple edges, take a multiset of pairs rather than a set.
3. A multigraph is an incidence structure consisting of a set V of vertices and a set E of edges, with a relation of incidence between V and E, having the property that each element of E is incident with exactly two elements of V. To allow loops, replace “exactly two” by “one or two”. This naturally extends to hypergraphs: for k-uniform hypergraphs, replace “exactly two” by “exactly k“; and for general hypergraphs, say “at least one”. It is slightly more difficult to define simple graphs in this picture. We have to impose the condition which is known in design theory as “no repeated blocks”, that is, two edges incident with the same set of vertices are equal.
4. Closely related is the statisticians’ definition: a multigraph is a block design with blocks of size 2. Then “regular” means “equireplicate”. Forbidding repeated blocks is not a natural thing to do in this context. Also, loops are unhelpful: if a block contains only one experimental unit, then we have no way of separating treatment effects from block effects for this unit.
5. A multigraph is a set F of flags with two partitions V and E of F satisfying the conditions that all parts of E have size 2, and a part of V and a part of E intersect in at most one flag. (Think of a flag as an incident vertex-edge pair; two flags lie in the same part of V, resp. E, if they share a vertex, resp.  an edge.) Loops are included by allowing E to have parts of sizes 1 and 2.

The last definition has the feature that it fits well with the case where the graph is a map, that is, drawn on an orientable surface. Then instead of partitions, we can take permutations υ and ε whose cycle partitions are V and E respectively (so that, in particular, ε is a fixed-point-free involution). Then ε corresponds to swapping the two flags on a given edge, and υ corresponds to traversing in the positive sense the flags on a given vertex.

If our interest is in directed graphs, another approach is possible. A digraph consists of a set V of vertices and a set E of edges, with two functions ι and τ from E to V (so that ι(e) and τ(e) are the initial and termimal vertices of e). This model naturally allows loops and multiple arcs. Forbidding loops means requiring that ι(e) ≠ τ(e) for all edges e.

Some special kinds of digraphs allow further options for the definition. For example, a tournament is an algebra (in the sense of universal algebra) with a single binary operation • satisfying the condition that v•w ∈ {v,w} for all elements v,w. The interpretation is that v•w is the terminal vertex of the arc joining v and w if the two are distinct, and v•v = v for all v.

Reflexive and transitive digraphs have two interpretations. On the one hand, they are categories in which for any two objects v,w there is at most one morphism from v to w. A more surprising interpretation is that these (if finite) are just finite topological spaces in disguise! In a finite topological space, draw an arc from v to w if every open set which contains w also contains v: this is a reflexive and transitive digraph. The digraph determines the topology, since any open set S is the union of the sets R(v) consisting of all points that can be reached by directed paths from v. Moreover, every reflexive and transitive digraph arises in this way: the sets R(v) are basic open sets for the corresponding topology.

Previous | Next