WorksMathematics
Discrete Spoilers: Introducing Abstract Undergraduate Mathematics Using Graph Theory
Abstract
Students often have serious difficulties with many key concepts of the undergraduate mathematics curriculum. We argue that many of these difficulties can be eased by explicitly separating the key ideas from the technical details. To do so, we present finite graphs as a setting where the basic concepts appear more transparently, because on a graph most proofs only require basic techniques from linear algebra. We illustrate this approach in three areas that cover a large part of the curriculum. First, we explain basic operators from vector calculus, such as the gradient and the divergence, through the incidence matrix of a graph. Second, we show that the diffusion equation has a simple solution on a graph. We also solve the graph Dirichlet problem, in which the values at some vertices are fixed. Third, we introduce a second incidence matrix that illustrates homology, cohomology and the Helmholtz decomposition in a simple way. Finally, we outline how to apply this approach to other branches of mathematics.
Introduction
In 1750, in a letter to Goldbach, Euler stated that a polyhedron with vertices, edges and faces satisfies [1]. This identity was “proven” by him soon after, and again by Cauchy in 1813. Yet that same year Lhuilier found polyhedra that did not satisfy the formula [2], such as a polyhedron with the shape of a picture frame, for which (Figure 1). These counterexamples forced mathematicians to change the statement of the theorem, its proof and even the definition of a polyhedron. Lhuilier himself showed that a polyhedron with tunnels satisfies . Later, Poincaré generalized the alternating sum to the Euler characteristic of a general space and related it to the Betti numbers of the space [1]. Overall, the full understanding of Euler’s formula required more than a century of collective work.
Figure 1. Left, a cube. Right, a polyhedron in the shape of a beveled picture frame, with a square tunnel through the middle. Below each polyhedron, the numbers , and of vertices, edges and faces, and the value of compared with 2. Dashed lines are hidden edges.
This history is a good illustration of the way mathematics advances. Mathematicians start from concrete cases, such as the cube and other convex polyhedra, make a conjecture and look for a proof. Using counterexamples, they can also refine the hypotheses that the theorem needs. At the end of the process, once they understand the problem, they extract a definition that condenses what they have learned [3]. In many courses, however, the order is the opposite. For example, a course on algebraic topology may define the Euler characteristic of a space as “the alternating sum of the dimensions of the quotients of the kernel of each boundary map by the image of the next one” before giving any motivation or example. Do we really expect students to understand this chain of abstract concepts without any preparation? More likely, students either understand very little and become frustrated, or learn to manipulate abstract concepts without understanding their meaning or the problems they are meant to solve [4]. In the latter case, they learn mathematics, but not how to think like a mathematician.
Of course, a course cannot reproduce every attempt and every counterexample that led to a definition. However, we can show students why we introduce a definition and which problem it aims to solve, before we present its technical version. In this article we argue that finite graphs are a natural setting to explore many abstract concepts of the undergraduate curriculum in this way [5, 6, 7, 8]. We see two reasons that make graphs an ideal didactic tool. First, graphs are accessible. We can draw a graph, and in a proof we can draw each step of the argument and see what it means on a particular graph. Hence a student can explore mathematical arguments with much less abstraction, in the same spirit as the exploration of concrete cases that we described above. Second, and most importantly, on a finite graph, the study of operators acting on functions reduces to the study of matrices acting on vectors. Hence the theorems that characterize these operators are based on linear algebra, a subject that students already know well, and the proofs are short and intuitive.
Therefore, if we first teach a problem in a discrete setting, the student can put all their mental effort into the problem itself. Why is the question interesting? How do we translate it into mathematical language? Which ideas lead to a proof? Only after the student has understood the object of study and the ideas behind it can we introduce the continuous version and the difficulties that require new mathematical tools (compactness, completeness, etc.). We can see a problem on a graph as a discrete spoiler of the more general problem: the graph version gives away the key idea, the “click” in the student’s mind, without all the development needed to reach it in the more difficult setting. Graph versions are also discrete spoilers, because the student realizes only later, with the hard version of the problem, that they were foreshadowing something important. In the rest of this article, we exemplify this approach in three areas of the curriculum: vector calculus, partial differential equations and algebraic topology. In § 2, we build the gradient and the divergence of a graph from its incidence matrix , with a model of opinions in a social network as motivation, and study the four fundamental subspaces of . In § 3, we solve this model, which is the graph version of the diffusion equation, and the analogous problem with zealots (people who never change their opinion), which is the graph version of the Dirichlet problem. In § 4, we build a curl by looking at the triangles of the graph and obtain homology, cohomology and the complete Helmholtz decomposition of the edge space. In § 5, we outline how to apply the same approach to other branches of mathematics. We end in Section 6 with a discussion of earlier work and of the limits of our approach.
Calculus on a graph
We start by motivating our framework with a question from everyday life. Several people discuss a topic, for example the quality of a film, with every person having an initial opinion on the film. Every day, each person talks only with his or her friends, and after each conversation the opinions of the two friends are closer than before. The pairs of friends form a graph , with a set of vertices, one for each person, and a set of edges, one for each pair of friends. We will assume that is undirected, unweighted and simple (no loops or multiple edges). We write for the number of vertices and for the number of edges. How do the opinions change in time? Do all the people reach an agreement, and on which opinion?
To answer these questions, we need a mathematical description of the opinions and a rule for the way in which they change. We will assume that the opinion of the person at each vertex at time is a real number , with large numbers for a good opinion and small numbers for a bad one. Mathematically, this assumption corresponds, at each time , to a function from to that assigns the real number to each vertex . Since is finite, this function is determined by its values , so we can identify it with the vector and the space of all opinions with . This finite description is very different from the case of functions from to , which form a space of infinite dimension and require formal tools from real analysis, such as suprema or Cauchy sequences. Already at this point, we see that working on a graph greatly reduces the technical tools that we need to do mathematics.1
For the rule that governs the evolution, we will assume that the opinions change in the simplest possible way. People change their opinion only through conversations with their friends. In a conversation, each friend is influenced by the other in the same way, so the two opinions move toward each other by the same amount. In particular, the friend with the larger opinion lowers it, while the friend with the smaller opinion raises it. Two friends with very different opinions have more to argue about than two friends who almost agree, so their opinions change faster. To model these assumptions, we introduce a flow of opinion along each edge, from the larger opinion to the smaller one, proportional to the difference between the two opinions. In other words, the flow along each edge is proportional to a discrete version of the derivative of the opinions.
How can we define a discrete derivative? In one dimension, the derivative of a function at a point is the limit of as . But on a graph, this limit has no meaning, because two vertices cannot be infinitely close. The smallest distance between two vertices is one, so we set and identify the point with a neighbor of , say, . The derivative of along the edge is then the difference . Note that the discrete derivative is a linear map between functions on two different sets, namely from functions on the vertices, in , to functions on the edges, in . In the continuum, the gradient also maps a function to a different kind of object, a vector field. However, the function and the vector field are defined on the same domain, so many students do not notice this change. On a graph, in contrast, this change is much more explicit, because the two functions are defined on different sets.
Our definition of the discrete derivative still has a problem. An undirected edge between and has no preferred endpoint, so we could equally take the difference . The first difference corresponds to the orientation of the edge from to , and the second one to the reverse. Which of the two should we choose? It turns out that the choice does not matter, as long as we use the same orientation throughout [9], so we will choose an arbitrary orientation for each edge. Figure 2 shows one such choice in an example with five people (we will refer to this graph as the house graph because of its shape). So, in summary, if we write for the vertex where an edge starts, the tail of , and for the vertex where it ends, the head of , then the discrete derivative of along , which we call the gradient of along and denote by , is

Figure 2. The house graph, with one person at each vertex and an edge between each pair of friends. Each edge is given an arbitrary orientation.
The gradient is linear in . On a graph, every linear operator on the functions on the vertices is a matrix, so we can write the gradient as the product of a matrix and the vector . What does this matrix look like? First, it must clearly be rectangular, with rows and columns. Since each row computes a difference between the two endpoints of , it must have a value in column , in column and zeros elsewhere. For example, for the house graph with the orientation of Figure 2, the matrix of the gradient is
Now that we have a notion of gradient, we can define the flow of opinion as the vector . Each component is the amount of opinion that moves along the edge per unit of time, positive if opinion moves from to and negative otherwise. We choose this definition by analogy with Fourier’s law, according to which the flow of heat is , with the temperature.
Our next goal is to combine the flows to deduce how the opinion at each vertex changes. The opinion at vertex changes at a rate equal to the net flow into , which is
We identify this net flow with minus the divergence of at , , by analogy with the continuum. Note that maps functions on the edges to functions on the vertices. We can once again find the matrix associated with this linear operator. Each row has the entry in the columns of the edges that start at , the entry in the columns of the edges that end at , and zeros elsewhere. For the house graph with the orientation of Figure 2, the matrix of the divergence is
But this matrix is minus the transpose of (1)! We defined the gradient as a discrete derivative and the divergence as a balance of flows, and yet the two operators have the same matrix up to a transpose and a sign. This identity is true for every graph, and as a result a single matrix is enough to describe both operators. We call the incidence matrix of the graph the matrix with if , if and otherwise, so that and . We use the name incidence because the nonzero entries of each column of indicate the two vertices incident to .
The four fundamental subspaces of
Before we go back to our model of opinions, let us see what the matrix tells us about the graph. Like any other matrix, has four fundamental subspaces, namely the kernel and the image of and of its transpose [10]. Do these subspaces contain information about the graph? We will see that, indeed, they describe its connected components, its cycles and its cuts.
We can find the kernel of directly. A vector satisfies if and only if it has the same value at the two endpoints of every edge. In that case, has the same value along every path, so it must be constant on each connected component. Conversely, every vector that is constant on each connected component satisfies . Hence , where is the number of connected components of the graph. In our model of opinions, the opinion vectors in produce no flow. Once we know the kernel of , we obtain the image of for free, as the two subspaces are orthogonal complements in , so consists of the vectors with zero sum on each connected component. This has a natural interpretation in our opinion model. represents the net change in opinions induced by a flow . Each flow transfers opinion from one vertex to another without changing the component’s total, so only opinion changes that preserve these totals are admissible. consists precisely of the admissible opinion changes.
Let us now look at the kernel of . Since , this kernel contains the flows with zero divergence, that is, the flows for which the total flow that enters each vertex is equal to the total flow that leaves it. The simplest way to obtain such a flow is to send one unit of flow around a cycle of the graph. We describe this flow with the vector that is equal to on the edges of the cycle whose orientation agrees with the direction of the flow, to on the other edges of the cycle and to elsewhere. By construction, this flow belongs to , and it can be proven that analogous flows around each cycle of the graph span the kernel of [9]. From now on, we will call every vector with a cycle. For example, on the house graph, the flows around the square and through the roof are the cycles and . In our model, a cycle is a flow that does not change any opinion.
Finally, let us look at the image of . To construct vectors in , we can choose opinion vectors and apply to them. Consider the indicator vector of a subset , which takes the value 1 on the vertices in and 0 on the vertices in its complement . With this choice, an edge can have nonzero flow only if it connects to . The set of edges connecting a vertex subset to its complement is called a cut in graph theory. Since every cut can be obtained from such a choice of , the space is spanned by all cut vectors, that is, by the vectors with an indicator vector. Figure 3 shows the cut of in the house graph, together with one vector in each of the other three subspaces.
Figure 3. Illustration of the four fundamental subspaces of the incidence matrix of the house graph, with the numbering and orientation of the left panel. For each subspace, we show one vector, both as a column vector and on the graph. For vectors of the vertex space , we write each entry inside its vertex and draw a thick border around the vertices with nonzero entries. For vectors of the edge space , we draw the edges with nonzero entries with thick lines and write these entries next to them. Top left, a constant opinion vector, in . Top right, the change of the opinions produced by one unit of flow along , in . Bottom left, the cut that separates the vertices 1 and 2 from the other vertices, in , which is also the flow produced by the opinion vector equal to 1 on the vertices 1 and 2 and to 0 on the other vertices. Bottom right, a flow with zero divergence, that is, a cycle, in . In the two bottom panels, the flow on an edge is positive if it goes in the direction of the orientation of the edge in the left panel, and negative otherwise.
We can now put all these pieces together to see how any flow on a graph can be decomposed. Since and are orthogonal complements in , every flow is, in a unique way, the sum of a gradient and a cycle. This is the graph version of the Helmholtz decomposition of a vector field into a gradient and a divergence-free field [6]. Students of vector calculus often meet the Helmholtz decomposition without a proof, since it requires tools that are typically introduced later in the curriculum. Here, in contrast, we obtain it directly from a basic result in linear algebra, namely that every vector decomposes uniquely into components belonging to two orthogonal complementary subspaces.
Diffusion dynamics on a graph
Let us now go back to our model of opinions. In this section, we will assume that is connected. In Section 2, we saw that the rate of change of the opinions is minus the divergence of the flow, which we can now write as . If we substitute the definition of the flow, , we obtain
We call the matrix the Laplacian of the graph, so that (2) becomes the diffusion equation . We choose these names to mimic the continuum, where the operator is the Laplace operator and the equation is the diffusion equation. is clearly symmetric, because , and positive semidefinite, because for every . We call the quantity
the energy of , by analogy with the elastic energy of a network of springs placed on the edges. In our model, measures the total disagreement of the opinions . It vanishes if and only if , that is, if and only if . Since is connected, is spanned by the vector with all entries equal to one. This implies that only for the multiples of , so is an eigenvalue of and its only eigenvectors are the multiples of . Moreover, the total opinion does not change in time, because belongs to the image of , whose vectors have zero sum.
The solution of the linear system of ODEs (2) is , with . To analyze this exponential, we will write in an orthonormal basis of eigenvectors , with eigenvalues . Because is positive semidefinite, all these eigenvalues are nonnegative. We expand the vector of initial opinions in this basis, , with and the usual inner product. Since , we obtain
Each component with decays exponentially at a rate equal to its eigenvalue. Since is connected, the only zero eigenvalue is , with . Hence, for large , converges to . In plain words, the opinion dynamics reach a steady state in which everybody agrees. This answers the question of § 2 about whether all the people reach an agreement. As for the opinion on which they agree, every opinion converges to , the average of the initial opinions.
Before we continue, let us look at these results from the point of view of a course on partial differential equations. While solving the model, we have derived with very little effort the graph versions of four important properties: the gradient and minus the divergence are adjoints of one another, the Laplacian is a positive semidefinite operator, the total opinion is conserved and the opinions converge to their average. All these facts follow from the factorization and from basic results of linear algebra. In contrast, the analog results in the continuum require tools and derivations that are far from elementary. For example, to prove that the gradient and minus the divergence are adjoint, that is, that for a function and a vector field on a domain , we need to assume that is bounded with a smooth boundary , that and are smooth enough, and that vanishes on . Similarly, proving that , with zero boundary values, has a basis of eigenfunctions with positive eigenvalues requires tools from functional analysis, such as the characterization of compact self-adjoint operators [11]. We hope the reader is thus convinced that the difficulties in the continuum come from the technicalities of analysis, not from the diffusion process itself.
Zealots and the Dirichlet problem
Let us now change the model. Suppose that some people, the zealots, never change their opinion. A zealot still talks with his or her friends and influences them. However, nobody influences the opinion of a zealot. We write for the set of vertices of the zealots and for the set of the other, influenceable, vertices. The opinion at each vertex is a fixed number , so the model becomes
We will focus on the stationary states of this model, which fulfill for every , that is,
In the continuum, (3) is the Dirichlet problem, in which we look for a function with in a domain and given values on its boundary . The zealots are the graph version of the boundary [5].
To interpret the condition in (3), let us see how the operator acts on the opinion vector . Using the definitions of discrete gradient and divergence, we obtain
with meaning that and are neighbors. Denoting by the degree of and the average opinion of its neighbors, we can express as
Hence, the condition states that the opinion at each vertex is the average of the opinions at the neighbors of . We say that is harmonic at if .
Ordering the vertices so that those of come first, we can write the linear system (3) in matrix form as
with and the submatrices of with rows in and columns in and in , respectively, and the vectors of the opinions in and in , the vector of the opinions of the zealots, and the identity matrix. The unknowns satisfy the system , in which the opinions of the zealots act as the inhomogeneous term. The structure of the solutions depends only on the invertibility of . Without zealots, is singular and the system has infinitely many solutions, corresponding to the multiples of discussed earlier in this section. With zealots, in contrast, is invertible and the system has exactly one solution. To prove this, let us show that the kernel of is trivial. Let satisfy , and let be equal to on and to on . Then , so is constant, and since vanishes on the nonempty set , we obtain and therefore .2 Since is square, it is then invertible, and the system (5) has exactly one solution, .
We have shown with relative ease that the Dirichlet problem on a graph has exactly one solution. In the continuum, uniqueness is still simple to prove, but existence is notoriously difficult. The reason is that, on a graph, we implicitly used uniqueness (the kernel of is trivial) to obtain existence (the system has a solution for any inhomogeneous term, i.e., is a surjective map). But in infinite dimension, a linear map with trivial kernel need not be surjective.3 A course on partial differential equations therefore must prove existence with other arguments. The standard method obtains the solution as the minimizer of the energy in a Hilbert space of functions with finite energy, and then uses regularity theory to show that this minimizer is a smooth harmonic function [11].
We end this section with a historical note. The idea of minimizing the energy goes back to Riemann, who in 1851 used it to prove the existence of a solution of the Dirichlet problem. In the proof, he assumed that some function with the given boundary values attains the minimum energy. But in 1870, Weierstrass gave an example of an energy with an infimum that no function attains, showing that Riemann’s proof had a gap. This gap was closed by Hilbert in 1900 [12]. Hence the existence of a minimizer, which on a graph can be proven by a first-year undergraduate, occupied Riemann, Weierstrass and Hilbert for half a century. Perhaps Riemann should have started with a graph.
Topology on a graph
In Section 2, we saw how the four fundamental subspaces of the incidence matrix describe the connected components, the cycles and the cuts of a graph. Less obviously, we can also use incidence matrices to describe the holes of a graph. The study of holes, called homology, is a central topic of algebraic topology. In the continuum, homology requires difficult tools like chain complexes [13]. However, if we formulate the problem on a graph, we can once again derive the key results using only linear algebra. The price to pay is that we need a new type of incidence matrix.
Our new matrix can be derived from the third basic operator of vector calculus, the curl. In the continuum, the curl measures how much a field circulates around infinitesimal closed paths. On a graph we cannot build infinitesimal loops, so we use the closest proxies for them: triangles. The curl of a flow should therefore return its circulation around each triangle of the graph.4 To compute this circulation, we give each triangle an arbitrary orientation (clockwise or counterclockwise), as we did with the edges, and add the flows on its three edges, with a plus sign if the orientation of the edge agrees with that of the triangle and a minus sign otherwise. As with the gradient and the divergence, we can write this operator as a matrix, which we will denote by , where is the number of triangles in the graph. Each row of this matrix indicates the three edges of one triangle, with the entry or depending on whether the orientation of the edge agrees with that of the triangle, and elsewhere. For example, the house graph has a single triangle, the roof, with the edges , and . If we orient it as , then
On the other hand, the transpose maps a vector , with one circulation per triangle, to the flow that these circulations produce on the edges. To distinguish from the incidence matrix of Section 2, from now on we will write for the latter.
What happens if we multiply and ? To answer this question, let us take a vector of circulations and the flow that it produces on the edges. then captures minus the divergence, i.e. the net amount of the flow that accumulates at the vertex. But a flow that only circulates around triangles cannot accumulate at any vertex (all the flow that enters a vertex through one of its edges must leave it through the next edge of the triangle). Hence for every , so
There is a profound interpretation of this identity. We can think of the two endpoints of an edge as its boundary. Similarly, the three edges of a triangle form its boundary. In these terms, the identity says that the boundary of the boundary of a triangle is zero. This statement is the graph version of one of the central identities of advanced mathematics, “the boundary of a boundary is zero”, which is the starting point of homology.
The identity also connects with seemingly unrelated identities from vector calculus. First, as we saw above, means that a circulation cannot accumulate flow at the vertices. Hence it is the graph version of the identity . Second, if we take transposes, we obtain . Since is the gradient and is the curl, this transposed identity is the graph version of . In terms of the fundamental subspaces, the two identities are the inclusions (every flow induced by circulations has zero divergence) and (every gradient flow has zero curl).
In vector calculus on , it is well known that the converse statements are also true: every field with zero curl is a gradient, and every field with zero divergence is the curl of another field. On a graph, however, the reverse inclusions can fail. For example, on the house graph, the cycle around the square has zero divergence but is not in (every flow of the form is zero on the edges that do not belong to a triangle, while is nonzero on , and ). This example shows that can be smaller than , so there are nonzero cycles in . Using the property , we can express this space as
(7) highlights that the flows in have simultaneously zero divergence and zero curl. We will call these flows harmonic. At first glance, the existence of these flows looks paradoxical. How can a flow neither accumulate at a vertex (zero divergence) nor go in circles (zero curl)? The way out of this paradox is that the curl only measures the circulation around triangles. A harmonic flow has zero circulation there, but it may circulate around longer cycles. What’s more, we can exploit these flows to extract structural information about the graph, like the location of its holes. For example, on the house graph, the harmonic flows (proportional to ) go around the square, the only hole, but split at the roof to force the circulation around the triangle to vanish.
A skeptical reader might doubt that this notion of hole captures the same idea as the empty center of a ring. However, mathematicians as early as Riemann have used the continuum analog of this definition to characterize holes [14]: a surface has a hole if we can find a closed curve on it that does not bound any part of the surface, that is, a closed curve that we cannot write as a sum of small loops within the region enclosed by the curve. To better understand why such a curve detects a hole, let us try to express the circulation along this curve, which we will call a global circulation, as a sum of local circulations, that is, circulations along small loops inside the region that it encloses. We will do this on two surfaces, a disk and a ring (Figure 4). For the disk (top left panel), any two neighboring local circulations go along their shared boundary in opposite directions and cancel out there. Thus, if we fill the whole disk with local circulations, they cancel everywhere except on the boundary of the disk. In other words, the global circulation along the boundary is the net effect of the local circulations in the interior.5 For the ring (top middle panel), we can apply the same argument, obtaining not one but two global circulations, one along the outer boundary and another along the inner one. For the outer global circulation, the local circulations that generate it are inside the region that it encloses, as for the disk. For the inner one, however, we run into the problem that the local circulations generating it are outside the region enclosed by it. We therefore cannot write this global circulation as a sum of local circulations in its interior. In fact, if we add local circulations on the surface of the ring, we can never obtain a global circulation along the inner boundary alone, it always comes together with one along the outer boundary circulating in the opposite direction.

Figure 4. Top, a disk (left) and a ring (middle) in the plane, with local counterclockwise circulations inside them, and the same ring with a flow that goes around the hole without local circulations (right). Bottom, triangulations of the disk and of the ring, with a counterclockwise circulation around each triangle (left and middle), and the harmonic flow of the triangulated ring (right), with thinner lines on the edges where its value is half. In the left and middle panels, the thick cycles are the global circulations that result from adding the local circulations.
If we triangulate the two surfaces (bottom row of Figure 4), the previous argument becomes the criterion behind Equation (7), with the cycles around the triangles in the role of the local circulations. In the triangulated disk, the cycle along the boundary is the sum of the cycles around all the triangles, so it is in and is not harmonic. In contrast, in the triangulated ring, we can find a harmonic flow, namely the one that goes counterclockwise along both the inner and the outer cycle, with the same value on all their edges, and it has half this value on the edges between them. By construction, this flow cannot be expressed as a sum of triangle circulations, since the circulation of this flow around every triangle is zero. In fact, looking at the bottom row of Figure 4, we can see a clear difference with the curl flow and the harmonic one: adding the circulations of all the triangles of the ring gives a flow that goes clockwise along the inner cycle (middle panel), while the harmonic flow goes counterclockwise along both cycles (right panel). Hence the holes that we found with and are analogous to the holes of the continuum.
So far, we have detected holes using and finding zero-divergence flows that cannot be expressed as combinations of cycles around triangles. But we could use and search for zero-curl flows that are not gradients. Since , the flows in but not in are again the harmonic flows (the flows in ), so this second way of searching detects the same holes. Once again, this point of view has a counterpart in the continuum. For example, a classical way of showing that has a hole is to study the field . This field has zero curl, but its circulation along the unit circle is , so it cannot be the gradient of any function. On a simply connected domain, the Poincaré lemma states that every field with zero curl is a gradient. Hence the existence of this field implies that its domain has a hole, which in this case is the origin. The search for holes with fields instead of curves is called cohomology. Detecting holes with curves and detecting them with fields are in fact equivalent approaches, but proving it is hard (this equivalence is known as de Rham’s theorem [15]). On a graph, however, the equivalence is an immediate consequence of the identity .
Let us now go back to Equation (7). In § 2.1, we commented that . Moreover, we know that . Hence
In words, every flow is, in a unique way, the sum of a gradient, a flow of circulations around triangles and a harmonic flow. Equation (8) is the complete version of the Helmholtz decomposition of § 2.1 [16, 6]. The harmonic part is nonzero only if the graph has holes, in the same way as the harmonic fields in the continuum.6
To summarize, with two incidence matrices, we have understood the identity “the boundary of a boundary is zero”, the holes of a space, the equivalence between homology and cohomology and the complete Helmholtz decomposition. In the curriculum, these results are spread over vector calculus in the first year and algebraic topology in the third year, if at all. They require chain complexes, singular homology and differential forms. On a graph, however, they are simple statements about the kernels and images of and . We did not need group theory, quotients or analysis. Quite a payoff for a first course on linear algebra.
Other branches of mathematics
Analysis and topology are not the only subjects in which technical details obscure simple ideas. Many other courses of the curriculum start with a demanding definition and reach the central idea only after many technical steps. In this section, we will sketch, without complete proofs, three additional subjects in which graphs show the main ideas in a transparent way.
Geometry
On a curved surface, such as a sphere, we can still define a Laplace-like operator, called the Laplace–Beltrami operator. To define it, however, we need a Riemannian metric, which tells us how to measure lengths and angles at each point of the surface. The expression of the Laplace–Beltrami operator [17] is notoriously scary,
where are local coordinates on the surface and is the matrix of the metric in these coordinates. Despite the intimidating expression of , the only new ingredient with respect to the usual Laplace operator is the metric. On a surface, we can always choose local coordinates in which is diagonal, with positive diagonal entries and . In these coordinates, the formula becomes
Up to the factor , the operator takes the derivative of in each direction, multiplies it by a positive weight and then takes the divergence. This is the structure of the weighted Laplacian of a graph. Let us put a positive weight on each edge , and let be the diagonal matrix with the weights on its diagonal. The weighted Laplacian is then , with the same gradient as in Section 2. Hence the weights give a gentle way to study how geometry changes the properties of the Laplacian, without inverse matrices, determinants or tensors.
Probability and stochastic processes
A central object of study in probability is the Markov process, a stochastic process in which the transition probabilities depend only on the current state. In particular, Brownian motion is used to model systems like the motion of a particle in a fluid or the fluctuations of stock prices. However, many important questions about Brownian motion can only be answered by solving partial differential equations. For example, the expected time that a Brownian particle needs to leave a region is the solution of a Poisson equation with Dirichlet boundary conditions.
When the number of states of a Markov process is finite, we can model it as a directed graph, with one vertex for each state and one edge for each possible transition, weighted by its probability [18]. Many properties of the process can then be studied through the properties of this graph. For instance, the process can go from any state to any other state if and only if the graph is strongly connected. Another example is that a strongly connected process is periodic (it can return to its starting state only at multiples of some integer larger than one) if and only if the lengths of all the cycles of the graph have a common divisor larger than one.
Brownian motion, in particular, can be modeled as a random walk on a connected undirected graph in which each vertex moves to each of its neighbors with probability . Interestingly, many expected times of this random walk can be computed, once again, with the Laplacian. For example, the expected time that the walk needs to leave a set of vertices is the solution of a linear system with the same matrix as the problem with zealots of Section 3. Similarly, the expected time that the walk needs to go from a vertex to a vertex and back, called the commute time, is , where are the entries of the pseudoinverse of [19]. Hence quantities that in the continuum require the solution of partial differential equations are, on a graph, simple expressions in terms of the Laplacian.
Optimization
Linear programming is one of the most useful tools of applied mathematics, with applications in logistics, economics, etc. A central result in the field is duality: every maximization problem has a dual minimization problem with the same optimal value. Students usually meet the dual problem as a formal recipe, which transposes the matrix of the problem and exchanges the roles of variables and constraints. The resulting problem seems to have no meaning of its own. Why should the maximum of one problem be equal to the minimum of a different one?
On a graph, both problems have a concrete meaning. Let us imagine that the edges are pipes, each with a capacity , and that we want to send as much water as possible from a vertex to a vertex . In the language of Section 2, we look for a flow with on every edge and with zero divergence at every vertex other than and . The dual problem looks for the cheapest way to block the water, that is, for a cut that separates from with the smallest total capacity. Every unit of water must cross every cut, so no flow can exceed the capacity of any cut. Less obviously, the largest flow is equal to the smallest cut. This result, known as the max-flow min-cut theorem [20], is a case of linear programming duality. Moreover, the maximization problem involves the divergence , while the minimization problem involves the gradient . Hence the transposition in the formal recipe of duality is simply a change of viewpoint from the divergence to the gradient.
Discussion
In this article, we have explored graphs as a setting in which to introduce key concepts of the undergraduate curriculum, such as the gradient, the divergence, the curl, the Laplacian, the diffusion equation, homology and the Helmholtz decomposition. Despite the diversity of these topics, most results were simple consequences of the properties of the kernels and images of incidence matrices. Hence, contrary to a common belief, understanding the central ideas of diffusion or homology, to name two examples, does not require an advanced knowledge of limits, function spaces or group theory. What students often perceive as difficult is not the central idea, but the analytic setting in which they first meet it. This does not mean that we should stop teaching the continuum. Instead, the continuum should come after the graph version, when the student already knows the central idea and can focus on the problems and subtleties of working over a continuum. In practice, a teacher needs only the linear algebra of a first course, so discrete spoilers can be introduced already in the second year of most curricula. A teacher can open each abstract topic with one or two lectures on its graph version, before introducing the continuous theory.
Several authors have already remarked that graphs can illustrate central results of their respective areas. For example, Doyle and Snell did so for random walks and potential theory [5], Lim for cohomology and Hodge theory [6], Knill for the theorems of Green–Stokes, Gauss–Bonnet and Poincaré–Hopf [7], and Grady and Polimeni for vector calculus and its applications to computational science [8]. Bamberg and Sternberg also introduced homology and cohomology to students of physics through electrical networks [21]. In contrast with these works, we propose graphs as a first setting for the curriculum as a whole. This proposal also challenges the widespread view that graphs should be taught primarily as models in applied mathematics. Graphs should also be leveraged in pure mathematics as a setting where a student can state a conjecture, test it on small examples and find the step where a proof fails.
A reader may object that we replace mathematics with a simplified imitation of it. Our answer is the maxim, usually attributed to Einstein, that everything should be made “as simple as possible, but not simpler”. The graph versions are more intuitive than the continuous counterpart, but they are complete, with hypotheses, theorems and proofs. Only the setting is simpler; the mathematical content is the same.
Discrete spoilers are not a universal remedy and have their limits. First, our arguments are mathematical and historical. We have not measured the effect of the approach on students, which would require an empirical study in real courses. Second, the approach works only for theories whose central idea is evident in finite dimension. For example, measure theory has a central difficulty, the existence of sets without measure, that is not present in discrete settings. Other areas, like set theory, have no graph version at all, because their central ideas already require an infinite setting.
Spoilers are dreaded because knowing the ending can be fatal to a mediocre story. In great stories, however, the question is never what happens, but how. Everyone knows that Achilles will die, that Troy will fall and that Odysseus will need twenty years to return home, and yet the Iliad and the Odyssey still move readers almost three thousand years later. Everybody who watches Tristan und Isolde knows that the lovers are doomed, but the four hours of musical longing make the final Liebestod a cathartic experience. Mathematics is one of these stories. Telling a student, before any limit or function space, that a harmonic function is the average of its neighbors, or that a hole is a cycle that bounds nothing, does not spoil analysis or topology. It motivates the student to read on. We hope that our discrete spoilers leave students eager to learn not only which results are true, but why.
Acknowledgments
The author thanks Karel Devriendt for insightful discussions. The author is also grateful to the podcast La vaca esférica, where he first heard the story of Euler’s formula as told by Lakatos, and with it the view of mathematics as a sequence of conjectures, refutations and better proofs. The author acknowledges funding from PID2022-141802NB-I00 (BASIC), funded by MCIN/AEI/10.13039/501100011033 and by “ERDF A way of making Europe”, and from Universidad Carlos III de Madrid through its Programa Propio de Investigación (Proyectos Jóvenes PPIT2025, project IDISC, 2025/00800/001).
References
- [1]Richeson DS. Euler’s Gem: The Polyhedron Formula and the Birth of Topology. Princeton (NJ): Princeton University Press; 2008.
- [2]Lhuilier S. Mémoire sur la polyédrométrie; contenant une démonstration directe du théorème d’Euler sur les polyèdres, et un examen des diverses exceptions auxquelles ce théorème est assujetti. Ann Math Pures Appl. 1812–1813; 3:169-89.
- [3]Lakatos I. Proofs and Refutations: The Logic of Mathematical Discovery. Worrall J, Zahar E, editors. Cambridge: Cambridge University Press; 1976.
- [4]Skemp R. Relational understanding and instrumental understanding. Mathematics Teaching. 1976; 77:20-6.
- [5]Doyle PG, Snell JL. Random Walks and Electric Networks. vol. 22 of Carus Mathematical Monographs. Washington (DC): Mathematical Association of America; 1984.
- [6]Lim LH. Hodge Laplacians on graphs. SIAM Rev. 2020; 62(3):685-715.arxiv.org/abs/1507.05379
- [7]Knill O. The theorems of Green–Stokes, Gauss–Bonnet and Poincaré–Hopf in graph theory; 2012. arXiv:1201.6049 [math.DG].arxiv.org/abs/1201.6049
- [8]Grady LJ, Polimeni JR. Discrete Calculus: Applied Analysis on Graphs for Computational Science. London: Springer; 2010.
- [9]Biggs N. Algebraic Graph Theory. 2nd ed. Cambridge Mathematical Library. Cambridge: Cambridge University Press; 1993.
- [10]Strang G. The fundamental theorem of linear algebra. Amer Math Monthly. 1993; 100(9):848-55.DOI
- [11]Evans LC. Partial Differential Equations. vol. 19 of Graduate Studies in Mathematics. 2nd ed. Providence (RI): American Mathematical Society; 2010.
- [12]Monna AF. Dirichlet’s Principle: A Mathematical Comedy of Errors and its Influence on the Development of Analysis. Utrecht: Oosthoek, Scheltema & Holkema; 1975.
- [13]Hatcher A. Algebraic Topology. Cambridge: Cambridge University Press; 2002.
- [14]Riemann B. Theorie der Abel’schen Functionen. J Reine Angew Math. 1857; 54:101-55.
- [15]de Rham G. Sur l’analyse situs des variétés à n dimensions. J Math Pures Appl. 1931; 10:115-200.
- [16]Eckmann B. Harmonische Funktionen und Randwertaufgaben in einem Komplex. Comment Math Helv. 1944–1945; 17:240-55.
- [17]Rosenberg S. The Laplacian on a Riemannian Manifold: An Introduction to Analysis on Manifolds. vol. 31 of London Mathematical Society Student Texts. Cambridge: Cambridge University Press; 1997.
- [18]Levin DA, Peres Y. Markov Chains and Mixing Times. 2nd ed. Providence (RI): American Mathematical Society; 2017. With contributions by Elizabeth L. Wilmer.
- [19]Chandra AK, Raghavan P, Ruzzo WL, Smolensky R, Tiwari P. The electrical resistance of a graph captures its commute and cover times. Comput Complexity. 1996; 6:312-40.
- [20]Ford LR, Fulkerson DR. Maximal flow through a network. Canad J Math. 1956; 8:399-404.
- [21]Bamberg P, Sternberg S. A Course in Mathematics for Students of Physics. vol. 2. Cambridge: Cambridge University Press; 1990.

