Abstract: This paper presents an elementary, self-contained, and purely combinatorial proof of the Rayleigh monotonicity property in graphs. By establishing a new polynomial identity that expresses the difference between spanning tree products as a perfect square of forest-generating polynomials, the authors bypass the traditional reliance on complex matrix algebra and determinants.
Introduction
Rayleigh’s Monotonicity Principle is a cornerstone of electrical network theory. It states that if the conductance of any edge in a network of resistors is increased, the overall effective conductance between any two nodes cannot decrease. While physically intuitive—adding more conductive material should not make a circuit more resistive—mathematical proofs have historically relied on the Matrix-Tree Theorem and Jacobi’s theorem on inverse matrix minors.
For combinatorialists, these "black box" algebraic proofs are often unsatisfying because they obscure the underlying discrete structure of the graph. This paper addresses the challenge by providing a proof rooted entirely in the language of spanning trees, cycles, and forests.
The Combinatorial Identity
The core of the proof is the transformation of an inequality into a precise combinatorial identity. Rayleigh monotonicity is equivalent to showing that for any two edges $e$ and $f$ in a graph $G$, a specific relationship between spanning tree counts holds. The authors prove Theorem 1, which states:
$$T^f_e(G)T^e_f(G) - T_{ef}(G)T^{ef}(G) = [X^+(G; e, f) - X^-(G; e, f)]^2$$
In this identity, $T$ represents various configurations of spanning trees (where edges $e$ and $f$ are either deleted or contracted). The terms $X^+$ and $X^-$ represent specific sets of spanning forests. Crucially, because the right side of the equation is a perfect square, the difference on the left must be non-negative for any real-valued edge weights. This "square trick" provides a combinatorial witness to the monotonicity property.
Methodology: Graph Reductions
The authors employ mathematical induction on the number of edges in the graph. To facilitate the inductive step, they reduce the problem by examining vertices with low degrees (specifically degrees 2, 3, and 4). By "merging" or "removing" these vertices, they show that if the identity holds for a smaller graph, it must hold for the larger one.
For the most complex reduction—a vertex of degree 4—the authors utilize a sign-reversing involution. This classic combinatorial tool allows them to cancel out unwanted terms in the polynomial expansion, ensuring the identity remains consistent across graph transformations.
Base Cases and Verification
To ground the inductive proof, the authors explicitly verify the identity for fundamental small graphs. These include $C_2$ (two parallel edges), $P_3$ (two incident edges), and $K_4$ (the complete graph on four vertices).
Verifying these base cases ensures that the inductive chain has a solid foundation. The $K_4$ case, depicted as a tetrahedron, is particularly important as it represents the smallest non-trivial planar graph where the interaction between multiple edges becomes complex.
Key Insights and Future Work
By avoiding the Matrix-Tree Theorem, this proof reveals why Rayleigh monotonicity holds based on the connectivity and cycle structure of the graph. The definition of $X^+$ and $X^-$ forests is particularly insightful: when edges $e$ and $f$ are added to these forests, they form a unique cycle. $X^+$ represents configurations where $e$ and $f$ are oriented in the same direction around that cycle, while $X^-$ represents opposite orientations. This captures the fundamental "interaction" between different parts of the electrical network.
While this proof is a significant step forward, the authors note it is not yet a "direct bijective proof," as it still relies on induction and case-by-case reductions. Future work may seek a non-inductive bijection that explains the identity in a single step. Additionally, while this proof is tailored to graphs, Rayleigh monotonicity also applies to regular matroids, suggesting that a further abstraction of this combinatorial approach may be possible.
Summary updated