Proof of `Characterization of Label-Connected Multigraphs`
groundedproofs/Lax630294Proofs/Final.lean · lax-630294
What this proof establishes
no assumptions
Assuming the claims on the left, the claim on the right holds — checked by the archive's pipeline. Proof code is not displayed here.
In the paper
- page 5 of this submission's paper
Strategy
Sufficiency: a -witness or an -witness is turned into a labeling by gathering secrets along the first tree or forest, exchanging them (through a hub edge, or around the cycle), and distributing them along the second one. Necessity: contract the maximal sets supporting two edge-disjoint spanning trees, bound the number of calls in the quotient from below by , split into the cases edges (a -witness) and edges (canonical form of the call order, a protected extension of a four-cycle to an -witness of the quotient, and a lift to the original graph through a compatible choice of ports).