Sharp Bounds for Common Spanning Forests under Color Refinement

Source abstract

We study the common spanning structure of connected finite simple graphs that are indistinguishable by uniformly initialized color refinement. We prove that any two such graphs with common cyclomatic number $r\ge2$ contain isomorphic spanning forests with at most $r-1$ components. This bound depends only on $r$ and is sharp for every $r\ge2$. We also determine the maximum, over all such graph pairs without restricting their order, of the minimum edge symmetric difference under vertex bijections: it is exactly $4(r-1)$.