Graph Representations

lax-683916·formalized by Clemens Kuske @clemenskuske · Codex (OpenAI)·registered·created ·GitHub @26253af·Lean v4.33.0 epoch · mathlib db584cd6d46c

Loading review…

Sign in with ORCID

Community review

Flags

Each flag is tied to a public ORCID identity and explains why this submission may be incorrect.

No flags have been submitted.

    Community review

    Flag this submission

    State precisely what appears incorrect. This explanation will be public under your ORCID name.

    Abstract

    Simple graphs occur in several formally distinct guises. This submission establishes precise bridges from SimpleGraphVSimpleGraph V to five of them: symmetric loopless digraphs, simple loopless multigraphs, spanning 2-uniform hypergraphs, 2-uniform edge set systems, and vertex-indexed neighborhood set systems.

    For digraphs, hypergraphs, edge set systems, and neighborhood set systems the comparison is an equivalence of the corresponding types. A simple multigraph is compared with a simple graph up to simultaneous vertex and edge isomorphism, because GraphαβGraph α β keeps ambient vertex and edge types. Looplessness of the hypergraph and edge-set-system representations is derived from 2-uniformity rather than recorded as redundant data.

    Neighborhood systems retain their vertex indexing: the neighborhood assigned to uu is exactly the set of vertices adjacent to uu. This indexing is what makes the construction invertible even when two vertices have the same open neighborhood.

    Together these results make the representation choice modular: a statement may be proved in the graph language best suited to it and transported across the appropriate equivalence or isomorphism, subject only to the usual isomorphism-invariance requirement in the multigraph case.

    Concepts

    Concept map
    11 concepts
    100%
    Proven claimDefinitionThis submissionA → B: B builds on A

    Proofs

    Proof networkview on GitHub

    100%
    assumptions conclusionProven claimClaim from this submissionProof — open large view for details
    Proof list

    Proof code is not displayed; the archive records each proof's checked relationship between claims.

    Related submissions

    No other submission in the archive builds on this one, and this one builds on none.

    Cite this

    This is only the formalizers. The authors of the formalized results may be different (see References).

    @misc{lax-683916,
      author = {Clemens Kuske and Codex (OpenAI)},
      title = {Graph Representations},
      year = {2026},
      howpublished = {Lax Archive, lax-683916},
      url = {https://laxarchive.org/lax-683916/},
    }

    Discussion

    Ask a question or add context. Endorsements and structured flags are kept in the review panel above.

    Loading discussion…