Multigraphs, Parallel Edges, and Loops

Why Edges Need Their Own Identities

In a simple graph, an edge is determined by its two endpoints: there is at most one edge between any two distinct vertices, and no edge joins a vertex to itself. In other settings, two vertices may be connected by several distinct edges, or an edge may begin and end at the same vertex. These features occur naturally when edges represent separate connections, roads, or events. To describe them without ambiguity, we must record edges as separate objects rather than as endpoint pairs alone.

Throughout this tutorial, graphs are finite and undirected. A multigraph is allowed to have loops and parallel edges. Some authors reserve “multigraph” for graphs without loops and use “pseudograph” when loops are allowed; the convention here permits both, and we will say explicitly when a particular example has no loops or no parallel edges.

Definition: A multigraph consists of a vertex set \(V\), an edge set \(E\) whose elements are distinct edge objects, and an assignment of two endpoints in \(V\) to each edge. The two endpoints are unordered and may be equal. An edge whose endpoints are the same vertex is a loop. Distinct edges with the same pair of endpoints are parallel edges.

For precision, write the endpoints of an edge \(e\) as the unordered pair \([u,v]\), allowing repetition: \([v,v]\) is the endpoint pair of a loop at \(v\). The edge set contains edge objects, not just these pairs. Thus two different edges \(e_1,e_2\) can both have endpoint pair \([u,v]\). The multiplicity of the pair \([u,v]\) is the number of edges with those endpoints. For a loop pair \([v,v]\), the multiplicity is the number of loops at \(v\).

Definition: A simple graph is a graph with no loops and no parallel edges. Equivalently, every edge joins two distinct vertices, and each unordered pair of distinct vertices is the endpoint pair of at most one edge.

Two distinct vertices are adjacent if at least one edge joins them. This tells us whether a connection exists, but not how many parallel edges there are. In a multigraph, the edge objects and their multiplicities carry information beyond adjacency.

Recognizing Simple Graphs Among Multigraphs

Proposition: A multigraph is simple if and only if it has no loop and every pair of distinct vertices is the endpoint pair of at most one edge.

Proof. Suppose first that the multigraph is simple. By definition, it has no loops. If some pair of distinct vertices were the endpoints of two or more edges, those edges would be parallel, also contradicting simplicity. Therefore every pair of distinct vertices is the endpoint pair of at most one edge. Conversely, suppose there are no loops and every pair of distinct vertices is the endpoint pair of at most one edge. The first condition excludes loops, and the second excludes parallel edges. These are exactly the two conditions required for the graph to be simple. \(\square\)

Worked Example: Two Parallel Edges

Let \(V=\{a,b,c\}\), \(E=\{e_1,e_2,e_3\}\), and assign endpoints \(e_1\mapsto[a,b]\), \(e_2\mapsto[a,b]\), and \(e_3\mapsto[b,c]\). There are no loops, but \(e_1\) and \(e_2\) are distinct edges with the same endpoints, so they are parallel. The multiplicity of \([a,b]\) is \(2\), and the multiplicity of \([b,c]\) is \(1\). By the proposition, this graph is not simple.

If we record only which distinct vertex pairs are joined, we get the simple graph with vertex set \(\{a,b,c\}\) and edge set \(\{ab,bc\}\). This record shows that \(a\) and \(b\) are adjacent, but it no longer shows that there are two separate edges between them.

Check: The original graph has three edge objects: two with endpoints \([a,b]\) and one with endpoints \([b,c]\). The reduced simple graph has only the two distinct endpoint pairs \(\{a,b\}\) and \(\{b,c\}\), confirming that the parallel-edge information has been discarded.

Degree Counts Edge Ends

For graphs with loops, degree must be defined in a way that accounts for both ends of every edge. An edge joining two different vertices contributes one end at each endpoint. A loop has two ends, and both are at its single endpoint. This convention is important even when the edge is drawn as a single loop or listed only once.

Definition: The degree of a vertex \(v\), written \(\deg(v)\), is the number of edge ends at \(v\), counting multiplicity. Equivalently, each non-loop edge incident with \(v\) contributes \(1\), each loop at \(v\) contributes \(2\), and an edge not incident with \(v\) contributes \(0\).

In a multigraph, an edge can be incident with a vertex more than once: a loop at \(v\) has both ends there. Counting edge ends therefore avoids the misleading shortcut of counting each incident edge object just once.

Proposition: Under the edge-end definition of degree, each loop at \(v\) contributes exactly \(2\) to \(\deg(v)\).

Proof. A loop has two endpoints, and by definition they are both \(v\). Thus the loop supplies two edge ends at \(v\). Since degree counts edge ends, rather than just the number of edge objects touching \(v\), this loop contributes \(2\) to \(\deg(v)\). \(\square\)

Worked Example: Degrees with a Loop and Parallel Edges

Let \(V=\{a,b,c\}\), \(E=\{e_1,e_2,e_3,e_4\}\), with endpoints \(e_1\mapsto[a,b]\), \(e_2\mapsto[a,b]\), \(e_3\mapsto[b,b]\), and \(e_4\mapsto[b,c]\). The graph has two parallel edges between \(a\) and \(b\), a loop at \(b\), and one edge between \(b\) and \(c\).

At \(a\), the edge ends come from \(e_1\) and \(e_2\), one each, so \(\deg(a)=1+1=2\). At \(b\), \(e_1\) contributes \(1\), \(e_2\) contributes \(1\), the loop \(e_3\) contributes \(2\), and \(e_4\) contributes \(1\). Thus \(\deg(b)=1+1+2+1=5\). At \(c\), only \(e_4\) is incident, contributing \(1\), so \(\deg(c)=1\).

Check: Counting the edge ends separately gives \(a\) two ends, \(b\) five ends, and \(c\) one end. In particular, the loop supplies two of the five ends at \(b\); counting it only once would give the incorrect value \(4\).

Worked Example: Several Loops at One Vertex

Let \(V=\{p,q,r\}\), \(E=\{f_1,f_2,f_3\}\), with endpoints \(f_1\mapsto[p,p]\), \(f_2\mapsto[p,p]\), and \(f_3\mapsto[p,q]\). Vertex \(r\) is isolated, meaning no edge has \(r\) as an endpoint.

Each of the two loops contributes \(2\) to the degree of \(p\), and edge \(f_3\) contributes \(1\). Therefore \(\deg(p)=2+2+1=5\). The only edge end at \(q\) is the endpoint of \(f_3\), so \(\deg(q)=1\). No edge end occurs at \(r\), so \(\deg(r)=0\).

Check: The two loops give four ends at \(p\), and the non-loop edge gives one end at \(p\) and one at \(q\). The counts are therefore \(5\), \(1\), and \(0\), as calculated.

Worked Example: A Loop Is Not a Parallel Edge

Let \(V=\{x,y\}\), \(E=\{g_1,g_2,g_3\}\), with endpoints \(g_1\mapsto[x,x]\), \(g_2\mapsto[x,y]\), and \(g_3\mapsto[x,y]\). The edge \(g_1\) is a loop at \(x\). The edges \(g_2\) and \(g_3\) are parallel because they are distinct and share the endpoint pair \([x,y]\). The loop is not parallel to either of them: its endpoint pair is \([x,x]\), not \([x,y]\).

The degrees are \(\deg(x)=2+1+1=4\) and \(\deg(y)=1+1=2\). The first contribution to \(\deg(x)\) is from the two ends of the loop; each of the parallel edges supplies one further end at \(x\).

Check: The loop contributes two ends at \(x\), and \(g_2\) and \(g_3\) contribute one end each at both \(x\) and \(y\). This gives four ends at \(x\) and two at \(y\), confirming both degree calculations.

Reducing a Multigraph to a Simple Graph

Sometimes a question asks only which distinct vertices are connected, not how many edges join them or whether there are loops. We can then form an underlying simple graph by keeping one edge for each distinct pair of different vertices that occurs as an endpoint pair, and discarding loops. This operation is useful for recording adjacency, but it does not preserve the full multigraph.

Proposition: Every finite multigraph determines an underlying simple graph whose edges are exactly the distinct pairs of different vertices joined by at least one edge in the multigraph. This construction discards loop information and the multiplicities of parallel edges.

Proof. Keep the original vertex set. For each unordered pair \(\{u,v\}\) with \(u\ne v\), include one edge exactly when at least one edge of the multigraph has endpoints \([u,v]\). Include no loops. The resulting graph has no loops by construction, and it has at most one edge for each pair of distinct vertices because each pair is included only once. It is therefore simple by the proposition above. A loop has equal endpoints and is never included; if several edges have endpoints \([u,v]\), the construction includes only one edge for that pair. Hence the construction discards both loop information and parallel-edge multiplicities. \(\square\)

This reduction is not reversible in general. For instance, a simple graph containing \(ab\) might come from one edge between \(a\) and \(b\), from several parallel edges, or from a multigraph that also has loops. The underlying simple graph alone cannot distinguish those possibilities.

Common Mistakes and a Reliable Check

Mistake: count a loop as one incident edge, then use that as its degree contribution. In the graph from the first degree example, this gives \(\deg(b)=1+1+1+1=4\), where the third \(1\) incorrectly counts the loop once. The correction is to count its two ends: \(\deg(b)=1+1+2+1=5\).

Mistake: treat a multigraph’s edge set as a set of endpoint pairs. If the two edges between \(a\) and \(b\) are both written simply as \(ab\), they collapse into one entry. Assigning distinct edge labels and recording each edge’s endpoints keeps both edges visible.

Mistake: call every repeated connection a loop. A loop has the same vertex at both endpoints, such as \([b,b]\). Parallel edges have the same two distinct endpoints, such as two separate edges with endpoints \([a,b]\). These are different features and can occur independently.

When reading or writing a multigraph, check the edge objects one by one: identify each pair of endpoints, note whether the endpoints are equal, and compare the endpoint pairs of distinct edges. For degree, count ends at the vertex, not just the edge objects that meet it. This procedure handles parallel edges, multiple loops, and isolated vertices without changing the underlying conventions.

Check Your Understanding

For each question, write the vertices and edge objects explicitly before deciding what the graph contains.

Let \(V=\{u,v\}\) and let two distinct edges both have endpoints \([u,v]\). Is this graph simple? What is the multiplicity of \([u,v]\)?
A vertex \(w\) has three loops and no other incident edges. What is \(\deg(w)\), and which edge-end count gives that value?
Let \(V=\{a,b,c\}\) and let the edge endpoint pairs be \([a,a]\), \([a,b]\), and \([a,b]\). Identify the loop and the parallel edges, then calculate each vertex degree.
What information is lost when a multigraph is replaced by its underlying simple graph?
State the two conditions that a multigraph must satisfy to be simple.