Multigraph

In the world of network science and mathematics, graphs composed of vertices and edges provide a powerful language for describing connections. From social networks to molecular structures, these models simplify complex realities into understandable forms. However, the most common type, the simple graph, imposes a strict rule: only one connection is allowed between any two points. What happens when this rule is too restrictive? How do we model systems with redundant internet cables, multiple flight routes between cities, or different types of chemical reactions between two substances? The elegant simplicity of simple graphs begins to fall short, creating a gap between our model and the rich complexity of the real world.

This article delves into the world of ​​multigraphs​​, a natural and powerful extension that embraces multiplicity. In the first chapter, "Principles and Mechanisms," we will explore the fundamental changes that occur when we allow multiple edges. We will redefine core concepts like vertex degree, examine which graph laws remain universal, and discover new structural properties that emerge from this added complexity. Following this, the "Applications and Interdisciplinary Connections" chapter will showcase the indispensable role of multigraphs in modeling real-world phenomena, from transportation networks and chemical kinetics to their surprising and profound connections with advanced mathematical fields like topology and knot theory. By the end, you will see that multigraphs are not just a complication, but a key to a deeper and more accurate understanding of a connected universe.

Let’s begin our journey in a familiar place. Imagine you are organizing a round-robin chess tournament. Every participant must play every other participant exactly once. How would you draw a map of this tournament? The most natural way is to represent each player with a dot (a ​​vertex​​) and each game with a line (an ​​edge​​) connecting two dots. The resulting picture is a model of your tournament. Notice the inherent rules: no player plays against themselves, so there are no edges that start and end at the same vertex. These are called ​​loops​​. Also, any two players compete only once, so there is at most one edge connecting any two vertices. A graph that abides by these two strict rules—no loops and no multiple edges—is called a ​​simple graph​​. For many problems, from social networks to tournament schedules, this elegant and tidy model is perfectly sufficient.

But what happens when our model needs to capture a reality that is messier, more robust, or more redundant? Picture yourself as a network engineer designing the backbone of the internet. If you have a critical connection to establish between two major data centers in New York and London, would you lay just one fiber optic cable? Certainly not. For fault tolerance and increased bandwidth, you would install multiple, independent physical links. How do we draw a map of this network? We could draw a single line and make a note beside it that says "3 cables," but that feels like a clumsy annotation, not part of the drawing itself. A more direct and honest representation would be to simply draw three distinct lines between the vertices for New York and London.

The moment we do this, we have broken the "at most one edge" rule. We have stepped out of the tidy world of simple graphs and into the richer, more expressive world of ​​multigraphs​​. By allowing ourselves this new freedom, we can model systems with redundancy, parallel pathways, and multiple types of relationships, all within the intuitive language of vertices and edges.

To navigate this expanded landscape, it helps to have clear definitions. Think of it as a hierarchy of graph types, where each level relaxes a rule and allows for more complexity.

• ​​Simple Graphs​​: This is the most restrictive class. They have no loops and no multiple edges. They are the bedrock of graph theory.

• ​​Multigraphs​​: Here, we lift the ban on multiple edges. You can have any number of edges connecting the same pair of distinct vertices. However, the prohibition against loops remains: no vertex can have an edge connecting to itself.

• ​​Pseudographs​​: This is the most general class. Here, all bets are off. Both multiple edges and loops are permitted. The name "pseudo" might sound pejorative, but it simply denotes the most permissive and general of these common graph types.

To get a feel for these creatures, let's consider the absolute simplest examples that showcase their unique features. What is the smallest possible multigraph that is not a simple graph? You need at least two vertices, and you connect them with two edges instead of one. This two-vertex, two-edge object is the most basic multigraph. What about the smallest pseudograph that isn't a multigraph? The feature that distinguishes it is the loop. The most minimal way to incorporate a loop is to have a single vertex with a single edge connecting that vertex to itself. This peculiar graph, with one vertex and one edge forming a loop, is a valid pseudograph but could never be a multigraph or a simple graph.

When we change the fundamental rules of what a graph can be, our basic methods of measurement must also adapt. Consider the ​​degree​​ of a vertex. In a simple graph, the degree is straightforwardly the number of edges connected to it, which is identical to the number of its neighbors.

In our new world, this equivalence breaks down. Imagine an engineer is designing a communication hub, represented by a vertex $v$. This hub must have a high capacity, which is modeled by requiring its degree to be exactly 4. However, due to physical limitations, it can only be adjacent to two other distinct nodes, $u$ and $w$. In the universe of simple graphs, this is a paradox: if $v$ has only two neighbors, its degree must be 2. But in a multigraph, the solution is simple: we can establish two parallel connections to vertex $u$ and two to vertex $w$. The number of neighbors is 2, but the degree is now $2+2=4$.

What if we allow loops? A loop is a single edge, but it has two ends, and both are attached to the same vertex. Therefore, a loop contributes 2 to the degree of its vertex. Our degree-4 hub could be built as a pseudograph with one edge to $u$, one edge to $w$, and one loop on itself for internal diagnostics. The degree would be $1+1+2=4$. This forces us to adopt a more robust definition: the degree of a vertex is the ​​number of edge-ends incident to it​​. This definition works universally, across all graph types.

Our mathematical tools must also evolve. An adjacency matrix for a simple graph uses 1s and 0s to indicate the presence or absence of an edge. For a multigraph, the entries must become integers, counting the multiplicity of edges between vertices. Interestingly, some tools are already equipped for this complexity. The ​​incidence matrix​​, which relates vertices to edges (not other vertices), handles multigraphs with grace. Each edge, even if it's one of several parallel edges, gets its own unique column in the matrix. The sum of the entries in a vertex's row is then, by definition, its degree. If a vertex $v_3$ has two edges connecting it to $v_1$ and three edges connecting it to $v_4$, the sum of the entries in the row for $v_3$ is simply $2+3=5$.

Amidst this flurry of new possibilities, do any of the old, fundamental laws still hold? Remarkably, one of the most elegant theorems in graph theory, the ​​Handshaking Lemma​​, remains steadfast. It states that the sum of the degrees of all vertices in any finite graph—simple, multi-, or pseudo-—is always an even number, precisely twice the total number of edges ($\sum_{v \in V} \deg(v) = 2|E|$). The reason is beautifully simple: every edge, no matter its type, has exactly two ends. Each end contributes 1 to the degree of some vertex. When we sum all the degrees, we are counting every edge-end, so the total sum must be twice the number of edges.

This simple truth has a powerful consequence: in any graph, the number of vertices with an odd degree must be even. This provides an immediate "sanity check" for any network diagram. It tells us, for instance, that it is physically impossible to construct a network with degree sequence $\{1, 2, 3, 3\}$, because it has three vertices of odd degree. The universality of this law across all graph types reveals its deep structural importance.

While some laws persist, the new structures give rise to novel properties. Consider two parallel edges between vertices $u$ and $v$. Together, they form the smallest possible cycle, a cycle of length 2: you can travel from $u$ to $v$ along one edge and immediately return to $u$ along the other. Now, a key theorem states that an edge can only be a ​​bridge​​ (an edge whose removal disconnects the graph) if it is not part of any cycle. Since any edge with a parallel partner is part of a 2-cycle, we arrive at a powerful conclusion: ​​an edge that is part of a set of multiple edges can never be a bridge​​. The redundancy that motivated the multigraph model in the first place manifests as a robust topological property.

This newfound structural richness also means that our old descriptors are less powerful. For simple graphs, the degree sequence tells us a great deal about the graph's structure. For multigraphs, it is much less definitive. It is entirely possible to have two completely different, ​​non-isomorphic​​ multigraphs that share the exact same degree sequence. For example, two different graphs on four vertices can both have the degree sequence $(3, 3, 2, 2)$. One might be a simple graph (a square with a diagonal), while the other might be a cycle with a double edge somewhere else. They have the same vertex degrees but are structurally distinct. The language of multigraphs is more expressive; it can describe a wider variety of structures.

You might be tempted to think of multigraphs as a niche, more complicated topic, separate from the clean world of simple graphs. But in truth, they are right next door, and sometimes you can stumble into their territory without even realizing it. Consider the common operation of ​​edge contraction​​. Take a simple graph, pick any edge $(u,v)$, and imagine shrinking it down until $u$ and $v$ merge into a single new vertex, $w$. What happens to the other edges? If there was another vertex $z$ that was connected to both $u$ and $v$ in the original graph, its edges now both connect to the new vertex $w$. And just like that, by performing a simple, intuitive operation on a simple graph, we have created a multigraph with a pair of parallel edges. This demonstrates that simple graphs and multigraphs are not distinct worlds, but points on a continuous landscape of graphical structures.

As we grow more comfortable in this landscape, we can ask more ambitious questions. In simple graphs, the concept of a ​​complement​​ is intuitive: for any two vertices, if there isn't an edge between them, draw one; if there is an edge, remove it. A wonderful property of this operation is that it is an ​​involution​​: the complement of the complement is the original graph. How could we extend this idea to multigraphs? If there are, say, 3 edges between $u$ and $v$, what is the complement of that? Is it 0 edges? 1 edge? The challenge is to find a definition that preserves the beautiful involution property.

This turns out to be a surprisingly subtle problem. Simple attempts fail. One successful, if somewhat artificial, solution is to first declare a universal "speed limit," a maximum number of parallel edges, $K$, that are allowed between any two vertices. Then, we can define the complement of a connection with $\mu$ edges to be one with $K-\mu$ edges. If we take the complement again, we get $K - (K-\mu) = \mu$ edges, which brings us right back to where we started. This is a profound lesson. Generalizing a simple idea isn't always about just loosening the rules. Sometimes, it requires the creative act of inventing a new rule or an external framework to preserve the properties we care about most. It shows that exploring these mathematical structures is a journey of discovery, constantly challenging our intuition and rewarding us with deeper, more unified understanding.

We have spent some time understanding the machinery of multigraphs—what they are and the properties that define them. You might be tempted to think of them as a minor complication, a footnote to the cleaner world of simple graphs. But nature, it turns out, is rarely simple. The real world is filled with redundancy, with multiple pathways, with repeated interactions. To ignore this is to draw a map that leaves out most of the roads. By embracing multiplicity, we unlock a far richer and more truthful language for describing the universe, from the architecture of our cities to the deepest structures of mathematics itself. Let's embark on a journey to see where these ideas take us.

The most immediate power of multigraphs lies in their ability to create more faithful models of the world around us. A simple graph can tell you if two things are connected; a multigraph can tell you how many ways or in what different manners they are connected.

Imagine modeling the transport system in a building with just two floors, a Ground Floor and a Penthouse. If there is a standard local elevator stopping at every floor and a dedicated express elevator that goes directly from the Ground Floor to the Penthouse, how do we draw this? In the language of simple graphs, we can only draw a single line between the two floors. This single line fails to capture the reality that there are two distinct transport systems available. A multigraph, however, handles this with elegance: the floors are vertices, and the two elevator lines become two parallel edges between them. This simple model immediately captures the idea of redundancy and choice. This same principle extends to vast transportation networks, where multiple roads, railway lines, or flight routes connect two cities.

The same idea applies to social structures. If we model a group of friends playing table tennis, a simple graph can show who has played whom. But what if two friends are avid rivals and have played dozens of games? A multigraph allows us to represent each game as a separate edge. The number of parallel edges between two people becomes a direct measure of the intensity of their interaction. If we also allow for solo practice sessions with a machine, we introduce loops—edges that start and end at the same vertex—turning our model into what is known as a pseudograph, an even more general structure.

This need for multiplicity becomes not just useful but absolutely essential in fields like chemistry. Consider a chemical reaction network. The reactions themselves are the edges of a graph, connecting reactant "complexes" (the vertices) to product complexes. Suppose we have a reaction where substance $A$ turns into substance $B$. It's entirely possible that this can happen through two different molecular pathways, each with its own distinct rate, say $k_1$ and $k_2$. A simple graph showing $A \to B$ would force us to merge these two processes, losing the crucial kinetic information that they are separate channels. The complex graph used in chemical reaction network theory is therefore inherently a multigraph. The parallel edges from $A$ to $B$ are not redundant; they are the model's way of telling us that nature has found two different ways to perform the same transformation, and the total rate of conversion is the sum of the rates of these parallel processes. Here, the multigraph is the only tool that tells the full story.

Once we have these richer models, the next question is what we can do with them. How do we navigate these complex landscapes?

Let's return to our transportation network, a multigraph where parallel edges represent different routes with different travel times (weights). If we want to find the absolute fastest way to get from Lab A to Lab E, we face a choice. Between any two labs, if there are multiple communication tunnels, a path-finding algorithm only cares about the fastest one. Any path that uses a slower, parallel tunnel can always be improved by switching to the fastest one. This gives us a beautiful and practical strategy: before running an algorithm like Dijkstra's, which is designed for simple graphs, we can "preprocess" our multigraph. We simply collapse each set of parallel edges into a single edge, assigning it the weight of the best option (e.g., the minimum latency).

However, not all problems are about finding a single best path. Sometimes, the goal is to traverse all connections. The classic "Seven Bridges of Königsberg" problem, which gave birth to graph theory, was a problem on a multigraph. It asked for an "Eulerian circuit"—a path that crosses every bridge exactly once and returns to the start. A connected multigraph has such a circuit if and only if every vertex has an even degree. While finding one such circuit is algorithmically straightforward, a graph can have many different Eulerian circuits. This raises a subtle but deep question: if we ask a computer to "find an Eulerian circuit," which one will it return? If the graph's vertices and edges are unlabeled, the choice is ambiguous. Different arbitrary starting points or choices along the way can lead to different resulting paths. Only by providing a labeled graph and a deterministic algorithm can we guarantee a unique, predictable output. The multiplicity of edges leads to a multiplicity of solutions, forcing us to be much more precise about what we are asking.

This is where our journey takes a turn, from the practical to the profound. It turns out that multigraphs are not just a convenient modeling tool; they are woven into the very fabric of graph theory itself, appearing in unexpected and beautiful ways.

One of the most magical ideas in graph theory is duality. For any graph drawn on a plane without edge crossings (a plane graph), we can construct its "dual" graph. Imagine the plane graph carving the surface into regions, or "faces." The dual graph has a vertex for each face, and two dual vertices are connected if their corresponding faces share an edge in the original graph. Now for the surprise: even if you start with a simple graph, its dual can be a multigraph! Consider a simple square (a 4-cycle). It has two faces: an "inside" and an "outside." Every single one of its four edges separates the inside from the outside. Therefore, the dual graph has two vertices (for the two faces) connected by four parallel edges. Multigraphs aren't an add-on; they are the natural reflection of simple structures.

This duality leads to some stunningly beautiful theorems. A graph is Eulerian (all its edges can be traversed in a single closed loop) if and only if every vertex has an even degree. A graph is bipartite if its vertices can be colored with two colors such that no two adjacent vertices share a color. These two properties seem unrelated. Yet, for planar graphs, duality links them in a perfect dance: ​​a planar graph is Eulerian if and only if its dual graph is bipartite​​. This is a profound statement of unity, connecting a dynamic property of motion (traversing edges) in one world with a static property of structure (coloring vertices) in its mirror image.

The necessity of multigraphs also reveals itself in the theory of edge coloring. For a simple graph, Vizing's famous theorem tells us that we can always color its edges with either $\Delta$ or $\Delta+1$ colors, where $\Delta$ is the maximum degree of any vertex. But if we allow multiple edges, this elegant bound can fail. For multigraphs, a different result, Shannon's Theorem, gives the upper bound $\chi'(G) \le \lfloor \frac{3}{2}\Delta(G) \rfloor$. Why does the proof for simple graphs break? The logic often involves building a "fan" of edges around a vertex and cleverly shifting colors. This procedure relies on the assumption that if you have different colored edges at a vertex, they must lead to different neighboring vertices. In a multigraph, this is no longer true! You can have several edges, all with different colors, leading to the very same neighbor. This single point causes the logical chain of the simple-graph proof to snap, forcing mathematicians to invent new, more powerful arguments.

The influence of multigraphs extends far beyond graph theory, providing a fundamental concept in other, seemingly disconnected, fields of science and mathematics.

In the abstract realm of matroid theory, which seeks to generalize the notions of independence from linear algebra and graph theory, multigraphs find a natural home. The "cycle matroid" of a graph captures the essence of its cyclic structure. A set of edges is a "circuit" in the matroid if it forms a minimal cycle in the graph. In this language, a loop in a graph becomes a circuit of size 1. And what about a pair of parallel edges? They form a minimal cycle of length 2, and thus correspond to a circuit of size 2 in the matroid. The visual intuition of parallel lines finds a crisp, algebraic fingerprint in this higher abstraction.

Perhaps the most spectacular application comes from the field of topology, in the study of knots. A knot is a tangled loop of string, and a central goal of knot theory is to find "invariants"—quantities you can calculate that are the same for two knots if they are truly the same knot, just rearranged. For a large class of knots called "alternating knots," there is an astonishing connection to graph theory. From a diagram of the knot, one can construct a "Tait graph." This graph's vertices represent regions in the diagram, and its edges represent the crossings. Crucially, this Tait graph is often a multigraph.

And here is the punchline: the determinant of the knot, a fundamental topological invariant, is exactly equal to the number of spanning trees in its Tait graph! For instance, to find the determinant of the knot known as $6_2$, one constructs its Tait graph, which happens to be a triangle with two parallel edges on each side. Using the Matrix-Tree Theorem from linear algebra, one can calculate that this multigraph has exactly 12 spanning trees. Therefore, the determinant of the $6_2$ knot is 12. Think about what has happened here: we took a topological object (a knot), translated it into a combinatorial object (a multigraph), and used a tool from linear algebra (a matrix determinant) to compute a number that tells us something fundamental about the original knot. This is a breathtaking example of the unity of mathematics, with the multigraph sitting right at the heart of the connection.

From city planning to chemical kinetics, from algorithmic design to the deepest structures of topology, multigraphs are not a mere curiosity. They are an essential part of the vocabulary we use to describe a complex world, a world of multiplicity, redundancy, and choice. By learning their language, we find that what at first seemed like a complication is, in fact, a key to a deeper and more beautiful understanding.