cycle_graph_le_cycle_with_two_chords
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$).
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`).
uses
le_sup_leftexact 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
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
/-- 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