simple_graph_is_longest_cycle
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
- simple_graph_is_cycle_subgraphA subgraph C of a simple graph G is a cycle if C is the subgraph traversed by a cycle walk in G.
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