simple_graph_is_fort
def
For a simple graph G on an arbitrary type V, a subset F of V is a fort if F is nonempty and for every vertex v not in F, it is not the case that there exists a unique vertex u in F adjacent to v in G (¬ ∃! u, u ∈ F ∧ G.Adj v u).
Statement
def simple_graph_is_fort {V : Type*} (G : SimpleGraph V) (F : Set V) : Prop
- Defined in
- arXiv:2611.01102 Sec. 2, Definition 2.1
- Verified
- 03 Nov 2026
- Axioms
- none listed
- Used by 4
- op_979_fort_transversal_number_empty_graphFor the edgeless graph (the empty graph bot) on a finite vertex set V with decidable equality, the fort transversal number equals the…
- simple_graph_fort_transversal_number_le_all_forts_transversal_numberFor any finite simple graph G, the fort transversal number T(G) is at most the transversal number of the family of all forts of G.
- op_979_csym_max_nullity_le_fort_transversal_numberFor every finite simple graph G on a finite type V with decidable equality, the combinatorially symmetric maximum nullity N(G) is at most…
- simple_graph_fort_transversal_numberThe fort transversal number T(G) of a finite simple graph G on a finite type V with decidable equality is the supremum of the transversal…
Read back from the Lean
For a type V, a simple graph G on V, and a subset F : Set V, simple_graph_is_fort G F asserts that:
1. F is non-empty, and
2. For every vertex v : V not in F, there does not exist a unique vertex u : V such that u ∈ F and v is adjacent to u in G (i.e., no vertex outside F has exactly one neighbor in F).
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 subset F of vertices is a fort if F is nonempty and no vertex outside F has a unique neighbor in F. -/ def simple_graph_is_fort {V : Type*} (G : SimpleGraph V) (F : Set V) : Prop := F.Nonempty ∧ ∀ v ∉ F, ¬ ∃! u, u ∈ F ∧ G.Adj v u