binary_function_graph_adj_const
lemmaverified
In the binary function graph of any simple graph on a nonempty vertex set, the constant false and constant true functions are adjacent.
Statement
lemma binary_function_graph_adj_const {V : Type*} [Nonempty V] (G : SimpleGraph V) : (binary_function_graph G).Adj (fun _ => false) (fun _ => true)
- Source
- arXiv:2610.37920 Section 2
- Verified
- 01 Nov 2026
- Axioms
Quot.soundpropext- Built on 1
- binary_function_graphThe binary function graph of a simple graph G is the graph with vertices V → Bool, where two distinct functions f and g are adjacent if…
Read back from the Lean
For every nonempty type $V$ and every simple graph $G$ on $V$, the constant false function fun _ => false and the constant true function fun _ => true (both of type $V \to \mathrm{Bool}$) are adjacent in binary_function_graph G.
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
/-- The constant false and constant true functions are adjacent in the binary function graph. -/ lemma binary_function_graph_adj_const {V : Type*} [Nonempty V] (G : SimpleGraph V) : (binary_function_graph G).Adj (fun _ => false) (fun _ => true) := by constructor · intro h obtain ⟨v⟩ := ‹Nonempty V› exact Bool.false_ne_true (congr_fun h v) · intro b have : {v : V | (fun _ => false) v = b ∧ (fun _ => true) v = b} = ∅ := by ext v; simp rw [this] exact Set.pairwise_empty _