Resonance graphs are a tool from mathematical chemistry that encode the structure of perfect matchings in a graph. A perfect matching is a way of pairing up every vertex of a graph with exactly one neighbor, which in chemistry corresponds to assigning double bonds in a molecule like benzene. The resonance graph captures how different such matchings relate to one another: two matchings are connected by an edge if they differ in a predictable, local way around a single face of the graph. Understanding the geometric and combinatorial properties of these resonance graphs helps chemists and mathematicians understand the space of possible bond arrangements in a molecule.
A median graph is a well-studied type of graph with a very clean structure: given any three vertices, there is always a unique "middle" vertex that lies on shortest paths between each pair of the three. Median graphs are intimately related to Cartesian products of trees and to hypercubes, and they appear naturally in many combinatorial settings. The Tratnik-Ye conjecture, posed several years ago, predicted that when you build a resonance graph from a surface-embedded graph and restrict attention to only some of the faces (a proper subset), each connected piece of the resulting resonance graph will always be a median graph. The conjecture was known in special cases but had not been settled in full generality.
The authors prove this conjecture completely, even in settings more general than previously studied, allowing the surface embedding to be non-cellular or non-strong and the graph to be non-bipartite. Their approach also shows that each face gives rise to a quotient structure that is a tree, and that these trees fit together to embed each component of the resonance graph isometrically into a Cartesian product of trees. As a bonus, they derive a clean criterion for when a natural embedding into a hypercube preserves distances exactly. The result closes a significant open problem and provides a unified geometric picture of how perfect matchings on surfaces are organized.