The Discrete Maximum Principle

Why Extremes Are Controlled by the Boundary

For a function on a finite graph, harmonicity says that each interior value is an average of neighboring values. An average cannot be larger than every value being averaged or smaller than every one of them. This elementary observation has a strong consequence: a harmonic function cannot have a strict maximum or minimum in the interior.

The key point is that the averaging condition propagates. If an interior vertex attains the global maximum, then all its neighbors must attain that same value. On a finite connected graph, following a path from that vertex eventually reaches the boundary. Thus the boundary controls the extreme values throughout the graph.

Graphs, Boundary, and Harmonicity

Throughout, let \(G=(V,E)\) be a finite, connected, undirected graph with no loops, and let \(B\subseteq V\) be a nonempty set of boundary vertices. The interior is \(I=V\setminus B\). Two vertices are neighbors if an edge joins them; write \(y\sim x\) for this relation, and let \(\deg(x)\) be the number of neighbors of \(x\).

Definition: A function \(u:V\to\mathbb{R}\) is harmonic on the interior \(I\) if, for every \(x\in I\), \[ u(x)=\frac{1}{\deg(x)}\sum_{y\sim x}u(y). \] Its values on \(B\) are boundary values; the harmonicity condition is imposed only at interior vertices.

Because \(G\) is connected and \(B\) is nonempty, every interior vertex has at least one neighbor, so the average in the definition is well-defined. A boundary vertex need not satisfy the averaging condition. It is the prescribed boundary data, not another equation to impose.

The Discrete Maximum and Minimum Principles

Theorem: If \(u:V\to\mathbb{R}\) is harmonic on \(I\), then \[ \max_{x\in V}u(x)=\max_{b\in B}u(b) \qquad\text{and}\qquad \min_{x\in V}u(x)=\min_{b\in B}u(b). \] In particular, every value of \(u\) lies between the smallest and largest boundary values.

Proof. Finiteness of \(V\) ensures that \(u\) attains a global maximum \(M=\max_{x\in V}u(x)\). Choose a vertex \(x\) with \(u(x)=M\). If \(x\in B\), then the maximum is already attained on the boundary. If \(x\in I\), harmonicity gives

M=u(x)=\frac{1}{\deg(x)}\sum_{y\sim x}u(y).

Every term in this average is at most \(M\). The average equals \(M\) only if every term equals \(M\), so \(u(y)=M\) for every neighbor \(y\) of \(x\). If one of these neighbors is interior, the same argument applies there. Choose a path from \(x\) to any boundary vertex, which exists by connectedness. Moving along the path, each interior vertex reached has value \(M\), and the averaging argument forces the next vertex to have value \(M\). The path therefore reaches a boundary vertex with value \(M\). Hence the maximum on \(V\) is attained on \(B\), proving the maximum identity. Apply this argument to the harmonic function \(-u\) to obtain the minimum identity. The stated bounds follow directly. \(\square\)

This proof also explains the propagation behind the result. An interior maximum forces all neighboring values to match it, and the same is true successively along any path through the interior. The analogous statement holds for an interior minimum.

Worked Examples

Worked Example: Linear Values on a Path

Take the path with vertices \(0,1,2,3\) and edges joining consecutive integers. Let \(B=\{0,3\}\), with \(u(0)=2\) and \(u(3)=8\). The interior vertices are \(1\) and \(2\). Harmonicity gives

u(1)=\frac{2+u(2)}{2}, \qquad u(2)=\frac{u(1)+8}{2}.

Writing \(u(1)=a\) and \(u(2)=c\), these equations become \(2a=2+c\) and \(2c=a+8\). Substituting \(c=2a-2\) into the second equation gives \(4a-4=a+8\), so \(a=4\) and \(c=6\). Check both averaging equations: \((2+6)/2=4\) and \((4+8)/2=6\). The boundary range is \([2,8]\), and the interior values \(4\) and \(6\) lie in that range.

Worked Example: A Star with Three Boundary Values

Let a center \(x\) be joined to three boundary vertices \(b_1,b_2,b_3\), with no other vertices or edges. Set \(u(b_1)=-2\), \(u(b_2)=1\), and \(u(b_3)=7\). The center is the only interior vertex, so its harmonic value must be

u(x)=\frac{-2+1+7}{3}=2.

Indeed, substituting this value into the defining equation gives \((u(b_1)+u(b_2)+u(b_3))/3=(-2+1+7)/3=2=u(x)\). The maximum principle gives \(-2\leq u(x)\leq 7\), as verified by the calculation. In this example the average is strictly between the smallest and largest boundary values because not all three boundary values are equal.

Worked Example: Two Coupled Interior Vertices

Consider vertices \(b_1,b_2,b_3,x,y\) and edges \(x\sim b_1\), \(x\sim b_2\), \(x\sim y\), and \(y\sim b_3\). Take \(B=\{b_1,b_2,b_3\}\) and assign boundary values \(0,6,3\), respectively. The harmonic equations are

u(x)=\frac{0+6+u(y)}{3}, \qquad u(y)=\frac{u(x)+3}{2}.

Substituting the second equation into the first gives \(u(x)=(6+(u(x)+3)/2)/3\). Multiplying by \(6\) yields \(6u(x)=12+u(x)+3\), so \(u(x)=3\), and then \(u(y)=(3+3)/2=3\). Direct checks give \((0+6+3)/3=3\) at \(x\) and \((3+3)/2=3\) at \(y\). Both interior values lie in the boundary range \([0,6]\).

Comparison and Uniqueness

The maximum principle also compares two functions using only their boundary values. This is useful when boundary data are ordered, and it gives uniqueness when the data agree.

Theorem: Let \(u,v:V\to\mathbb{R}\) both be harmonic on \(I\). If \(u(b)\leq v(b)\) for every \(b\in B\), then \(u(x)\leq v(x)\) for every \(x\in V\). Consequently, there is at most one function harmonic on \(I\) with any given boundary values.

Proof. Define \(w=u-v\). At each interior vertex, subtracting the two averaging equations shows

w(x)=\frac{1}{\deg(x)}\sum_{y\sim x}w(y),

so \(w\) is harmonic on \(I\). On the boundary, \(w(b)\leq 0\). The maximum principle implies

\max_{x\in V}w(x)=\max_{b\in B}w(b)\leq 0.

Thus \(w(x)\leq 0\) everywhere, which is \(u(x)\leq v(x)\). If \(u\) and \(v\) have the same boundary values, the comparison applies in both directions: \(u\leq v\) and \(v\leq u\). Therefore \(u=v\) on \(V\), proving uniqueness. \(\square\)

For any harmonic function with prescribed boundary values, the maximum and minimum principles also give the explicit bounds

\min_{b\in B}u(b)\leq u(x)\leq \max_{b\in B}u(b) \qquad (x\in V).

These statements concern what must hold if a solution exists. The maximum principle alone is not an existence proof; it establishes bounds and rules out competing solutions with the same boundary data.

Why the Assumptions Matter

Connectedness and a nonempty boundary are essential for these conclusions. If a graph has an interior component disconnected from the boundary, a constant can be added on that component without changing any boundary values or the harmonic equations there. Uniqueness can then fail, and the boundary values need not bound the values on that component.

The finite-graph setting also matters to the argument: it guarantees that a maximum and minimum are attained. The proof uses an attained maximum and follows a path to the boundary; it does not apply unchanged to an infinite graph, where a bounded function might approach its supremum without attaining it.

A common mistake is to impose harmonicity at boundary vertices as well as in the interior. In a boundary-value problem, the boundary values are specified, while the averaging equations determine interior values. Another is to infer that every interior value must be strictly between the boundary extremes. The principles give non-strict bounds. Equality can occur, for example when all boundary values are equal and the harmonic function is constant.

Key takeaway: On a finite connected graph with nonempty boundary, an interior extremum propagates along the graph until it reaches the boundary. This gives boundary bounds, comparison, and uniqueness for harmonic boundary-value solutions.

Check Your Understanding

Use the definitions and principles above to answer these questions.

Why does an average of neighboring values equal to the global maximum force every neighbor to have that maximum value?
Which assumptions ensure that a path from an interior vertex reaches the boundary?
If two harmonic functions agree on the boundary, what function can be formed from their difference, and how does the maximum principle apply to it?
Can an interior vertex attain the maximum when all boundary values are smaller? Explain using the propagation argument.
Why does the maximum principle not, by itself, establish that a solution exists for every choice of boundary values?

What You'll Learn