While this submission is a draft, it cannot be used by other submissions.

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.

Read the Lean proof on GitHub

In the paper

  • page 5 of this submission's paper

Strategy

Sufficiency: a TT-witness or an MM-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 2r−42r - 4, split into the cases 2r−32r - 3 edges (a TT-witness) and 2r−42r - 4 edges (canonical form of the call order, a protected extension of a four-cycle to an MM-witness of the quotient, and a lift to the original graph through a compatible choice of ports).