AFTD Auto-Formalizing Theoretical Domains

cycle_graph_le_cycle_with_two_chords

theoremverified

The cycle graph on m vertices is a subgraph of the cycle graph on m vertices with two chords added.

Statement

theorem cycle_graph_le_cycle_with_two_chords (m a : ℕ) :
    SimpleGraph.cycleGraph m ≤ cycle_with_two_chords m a
Source
arXiv:2610.17884 Lemma 4.1
Verified
25 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1
  • cycle_with_two_chordsThe simple graph on vertices 0, ..., m - 1 obtained from the cycle graph on m vertices by adding two chords: one between vertex 0 and…

Read back from the Lean

For all natural numbers $m$ and $a$, the cycle graph on $m$ vertices (SimpleGraph.cycleGraph m) is a subgraph of (i.e., less than or equal to in the graph order) cycle_with_two_chords m a.

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

The proof, explained

By definition, the cycle graph with two chords is the join (graph union) of the cycle graph $C_m$ and an auxiliary graph containing the two chords. The theorem follows immediately from the general lattice property that an element is less than or equal to its join with any other element ($a ≤ a ⊔ b$).

  1. The cycle graph on $m$ vertices is a subgraph of the cycle graph with two chords ($C_m ≤ C_m ⊔ \\dots$).

    By definition, `cycle_with_two_chords m a` is the join of `SimpleGraph.cycleGraph m` and a graph representing the two chords. Because simple graphs on a fixed vertex set form a semilattice under edge inclusion (subgraph ordering), the claim follows directly from the general lattice property that $a ≤ a ⊔ b$ (`le_sup_left`).

    line 4

    uses le_sup_left

      exact le_sup_left
le_sup_left
In any join-semilattice, every element is less than or equal to its supremum with another element ($a ≤ a ⊔ b$).

Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.

Lean source view module on GitHub

/-- The m-cycle embeds into the cycle with two chords. -/theorem cycle_graph_le_cycle_with_two_chords (m a : ℕ) :    SimpleGraph.cycleGraph m ≤ cycle_with_two_chords m a := by  exact le_sup_left
See it in the graphDiscuss this resultChallenge it