A combinatorial proof of Rayleigh monotonicity for graphs

Josef Cibulka, Jan Hladký, Mathieu Lacroix, D.g. WagnerarXiv 2008 · DOI · arXiv

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.

Illustrates the configurations used in the reduction of a degree-3 vertex, a key step in the inductive proof.

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).

The $K_4$ graph, one of the fundamental base cases used to verify the combinatorial identity.

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

Abstract

We give an elementary, self-contained, and purely combinatorial proof of the Rayleigh monotonicity property of graphs.
BibTeX
@misc{cibulka2008combinatorial,
  author = {Josef Cibulka and Jan Hladký and Mathieu Lacroix and D.G. Wagner},
  title = {{A combinatorial proof of Rayleigh monotonicity for graphs}},
  year = {2008},
  eprint = {0804.0027},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/0804.0027},
}
Figure