Multigraphs: Loops and Multiple Edges

Consider a graph in which the vertices represent cities and the edges represent highways. Certain pairs of cities are joined by an edge while other pairs are not. The graph may or may not be connected (although a disconnected graph is likely to result in disgruntled commuters). However, certain aspects of real highway networks are not captured by this model. First, between two nearby cities, there can actually be several interconnecting highways, and traveling on one of them is fundamentally different from traveling on another. This leads to the concept of multiple edges, , allowing for more than one edge between two adjacent vertices. Also, we could have a highway which leaves a city, goes through the nearby countryside and the returns to the same city where it originated. This leads to the concept of a loop, , an edge with both end points being the same vertex. Also, we can allow for more than one loop with the same end point.

Accordingly, authors frequently lead off a discussion on a graph theory topic with a sentence or two like:

1. In this paper, all graphs will be simple, , we will not allow loops or multiple edges.

2. In this paper, graphs can have loops and multiple edges.

The terminology is far from standard, but in this text, a graph will always be a simple graph, , no loops or multiple edges. When we want to allow for loops and multiple edges, we will use the term multigraph. This suggests the question of what we would call a graph if it is allowed to have loops but not multiple edges, or if multiple edges are allowed but not loops. If we really needed to talk about such graphs, then the English language comes to our rescue, and we just state the restriction explicitly!