AFTD Auto-Formalizing Theoretical Domains

simple_graph_is_longest_cycle

def

A subgraph C of a simple graph G is a longest cycle if it is a cycle subgraph and its vertex set has maximum cardinality among all cycle subgraphs of G.

Statement

def simple_graph_is_longest_cycle {V : Type*} {G : SimpleGraph V} (C : G.Subgraph) : Prop
Defined in
arXiv:2611.07145 Sec. 1
Verified
08 Nov 2026
Axioms
none listed
Built on 1

Read back from the Lean

For a type V, a simple graph G on V, and a subgraph C of G, simple_graph_is_longest_cycle C asserts that: 1. C is a cycle subgraph of G, meaning there exists a vertex v : V and a walk p : G.Walk v v such that p is a cycle (p.IsCycle) and the subgraph corresponding to p equals C (p.toSubgraph = C); and 2. For every subgraph C' of G, if C' is also a cycle subgraph of G, then the cardinality of the vertex set of C' (C'.verts.ncard) is less than or equal to the cardinality of the vertex set of C (C.verts.ncard).

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

Lean source view module on GitHub

/-- A cycle subgraph C is a longest cycle in G if its vertex set has maximal cardinality among all cycle subgraphs. -/
def simple_graph_is_longest_cycle {V : Type*} {G : SimpleGraph V} (C : G.Subgraph) : Prop := simple_graph_is_cycle_subgraph C ∧ ∀ C' : G.Subgraph, simple_graph_is_cycle_subgraph C' → C'.verts.ncard ≤ C.verts.ncard
See it in the graphDiscuss this resultChallenge it