Proof of `Multigraph representation of a simple graph`
groundedproofs/Lax683916Proofs/SimpleGraphMultigraphRepresentation.lean · lax-683916
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.
Description
The canonical multigraph has all vertices, uses unordered vertex pairs as its edge type, and retains exactly the edges of the simple graph.
Proof strategy
Use mathlib's . Its looplessness follows from the simple graph's irreflexivity, and its endpoint equation makes parallel edges impossible. The full vertex set is equivalent to the original vertex type, the edge equivalence is the identity, and incidence preservation unfolds to the defining endpoint equation.
Attribution
Directly from .