op_1371_min_forcing_num_upper_bound_achievable
There exists a natural number n, a bipartite simple graph G on Fin n, a field F with ringChar F ≠ 2, such that G admits an involutory weighted adjacency matrix over F, and there exists a natural number k such that either 4 ≤ k, Even k, and graph_min_forcing_num (G □ SimpleGraph.pathGraph k) = ((n / 2 * (k / 2) : ℕ) : ℕ∞), or 3 ≤ k, Odd k, and graph_min_forcing_num (G □ SimpleGraph.pathGraph k) = ((n * (k - 1) / 4 : ℕ) : ℕ∞) + graph_min_forcing_num G.
Statement
theorem op_1371_min_forcing_num_upper_bound_achievable : ∃ (n : ℕ) (G : SimpleGraph (Fin n)) (F : Type) (_ : Field F), G.IsBipartite ∧ ringChar F ≠ 2 ∧ graph_admits_involutory_weighted_adj_matrix G F ∧ ∃ k : ℕ, (4 ≤ k ∧ Even k ∧ graph_min_forcing_num (G □ SimpleGraph.pathGraph k) = ((n / 2 * (k / 2) : ℕ) : ℕ∞)) ∨ (3 ≤ k ∧ Odd k ∧ graph_min_forcing_num (G □ SimpleGraph.pathGraph k) = ((n * (k - 1) / 4 : ℕ) : ℕ∞) + graph_min_forcing_num G)
- Formalizes
- arXiv:2611.11813 Remark 2.10
- Verified
- 11 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 3
- graph_min_forcing_numThe minimum forcing number graph_min_forcing_num G of a simple graph G is the infimum in ℕ∞ of the extended cardinalities S.edgeSet.encard…
- graph_admits_involutory_weighted_adj_matrixA simple graph G on a finite vertex type V admits an involutory weighted adjacency matrix over a field F if there exists a matrix A over F…
- graph_is_forcing_matchingA subgraph S of a simple graph G is a forcing matching if S is a matching and there is a unique perfect matching M of G with S ≤ M.
- Used by 1
- op_1371_odd_improved_upper_bound_achievableThere exists a natural number n, a bipartite simple graph G on Fin n, a field F with ringChar F ≠ 2, and a natural number k such that G…
Read back from the Lean
There exist a natural number $n$, a simple graph $G$ on vertex set $\mathrm{Fin}(n)$, a type $F$, and a field structure on $F$ such that: 1. $G$ is bipartite; 2. the characteristic of $F$ is not 2; 3. $G$ admits an involutory weighted adjacency matrix over $F$; and 4. there exists a natural number $k$ such that either: - $4 \le k$, $k$ is even, and the minimum forcing number of the Cartesian product $G \mathbin{\square} \mathrm{pathGraph}(k)$ equals $(n / 2) \cdot (k / 2)$ (using integer division on $\mathbb{N}$, cast to $\mathbb{N}_\infty$); or - $3 \le k$, $k$ is odd, and the minimum forcing number of $G \mathbin{\square} \mathrm{pathGraph}(k)$ equals $(n(k - 1) / 4 : \mathbb{N}_\infty) + \mathrm{graph\_min\_forcing\_num}(G)$ (using integer division on $\mathbb{N}$, cast to $\mathbb{N}_\infty$).
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
The theorem asserts the existence of an $n$-vertex bipartite graph $G$ admitting an involutory weighted adjacency matrix over a field $F$ of characteristic $\ne 2$, such that the minimum forcing number of $G \square P_k$ matches an upper bound for some $k$. The proof constructs an explicit witness using the degenerate empty graph on $n = 0$ vertices, the rational field $\mathbb{Q}$, and path parameter $k = 4$. An auxiliary lemma establishes that any graph on an empty vertex type has minimum forcing number 0, allowing the forcing number equality $0 = (0/2) \cdot (4/2)$ and all empty-type algebraic and graph-theoretic properties to hold vacuously.
The empty subgraph $\bot$ is a forcing matching of $G$.
Unfolding the definitions of a forcing matching, matching, and perfect matching, all conditions consist of universal quantifications over the vertex type $V$. Because $V$ is empty, all conditions hold vacuously by `IsEmpty.false`. Furthermore, any subgraph of $G$ is empty, so $\bot$ is the unique perfect matching containing $\bot$.
uses
False.elim,IsEmpty.false,le_rfldsimp [graph_min_forcing_num] have hS : graph_is_forcing_matching G ⊥ := by dsimp [graph_is_forcing_matching, SimpleGraph.Subgraph.IsMatching, SimpleGraph.Subgraph.IsPerfectMatching, SimpleGraph.Subgraph.IsSpanning] refine ⟨fun v _ => False.elim (IsEmpty.false v), ?_⟩ refine ⟨⊥, ⟨⟨fun v _ => False.elim (IsEmpty.false v), fun v => False.elim (IsEmpty.false v)⟩, le_rfl⟩, ?_⟩ rintro M ⟨⟨_, _⟩, _⟩ ext v · exact False.elim (IsEmpty.false v) · exact False.elim (IsEmpty.false v)
The cardinality of the edge set of $\bot$ is 0.
An edge in $G$ consists of an unordered pair of vertices from $V$. Since $V$ has no elements, the edge set of the empty subgraph $\bot$ is empty ($\emptyset$). By `Set.encard_empty`, its cardinality is 0.
uses
False.elim,IsEmpty.false,Set.encard_emptyhave he : (⊥ : G.Subgraph).edgeSet.encard = 0 := by rw [show (⊥ : G.Subgraph).edgeSet = ∅ by ext e rcases e with ⟨u, v⟩ exact False.elim (IsEmpty.false u)] exact Set.encard_empty
The minimum forcing number of $G$ is 0.
The minimum forcing number is the infimum of edge counts over all forcing matchings. Since $\bot$ is a forcing matching with 0 edges, the infimum is at most 0 by `iInf_le` and `le_trans`. Because extended natural numbers are bounded below by 0 (`bot_le`), anti-symmetry (`le_antisymm`) shows the infimum is exactly 0.
uses
le_antisymm,iInf_le,le_trans,bot_leapply le_antisymm · have hle : (⨅ S, ⨅ (_ : graph_is_forcing_matching G S), S.edgeSet.encard) ≤ ⨅ (_ : graph_is_forcing_matching G ⊥), (⊥ : G.Subgraph).edgeSet.encard := iInf_le _ ⊥ have hle2 : (⨅ (_ : graph_is_forcing_matching G ⊥), (⊥ : G.Subgraph).edgeSet.encard) ≤ (⊥ : G.Subgraph).edgeSet.encard := iInf_le _ hS have hle3 := le_trans hle hle2 rwa [he] at hle3 · exact bot_le
It suffices to verify the existential statement for $n = 0$, $G = \bot$ on $\text{Fin } 0$, $F = \mathbb{Q}$, and $k = 4$.
We choose $n = 0$, the empty graph $\bot$ on $\text{Fin } 0$, the field $\mathbb{Q}$, and $k = 4$. The parity and inequality requirements for the even alternative ($4 \le 4$ and $4$ is even) hold immediately by `le_rfl` and $4 = 2 \times 2$, leaving the graph-theoretic properties and the forcing number equation to be verified.
uses
inferInstance,Or.inl,le_rflrefine ⟨0, ⊥, ℚ, inferInstance, ?_, ?_, ?_, 4, Or.inl ⟨le_rfl, ⟨2, rfl⟩, ?_⟩⟩
The empty graph on $\text{Fin } 0$ is bipartite.
A 2-coloring of the vertices of $\bot$ and the condition that adjacent vertices have different colors hold vacuously because $\text{Fin } 0$ has no elements (`Fin.elim0`).
uses
Fin.elim0· refine ⟨⟨fun x => Fin.elim0 x, fun {u} => Fin.elim0 u⟩⟩
The characteristic of $\mathbb{Q}$ is not 2. automation
The ring characteristic of the field $\mathbb{Q}$ is 0, which is not equal to 2; Lean's simplifier evaluates the characteristic and discharges the goal.
· simpThe empty graph on $\text{Fin } 0$ admits an involutory weighted adjacency matrix over $\mathbb{Q}$.
We witness the $0 \times 0$ zero matrix. Because $\text{Fin } 0$ is empty, the condition that nonzero entries correspond to edges holds vacuously via `Fin.elim0`. Similarly, the matrix equality $0 \cdot 0 = 1$ on an empty index set holds vacuously.
uses
Fin.elim0· dsimp [graph_admits_involutory_weighted_adj_matrix] use 0 constructor · intro u; exact Fin.elim0 u · ext i; exact Fin.elim0 i
The minimum forcing number of $G \square P_4$ equals $(0 / 2) \cdot (4 / 2) = 0$.
The vertex set of the Cartesian product graph $G \square P_4$ is $\text{Fin } 0 \times \text{Fin } 4$, which is empty. By the auxiliary lemma, its minimum forcing number is 0. Since $(0 / 2) \cdot (4 / 2) = 0$, the equality holds by reflexivity.
uses
op_1371_min_forcing_num_upper_bound_achievable_min_forcing_num_of_isEmpty· rw [op_1371_min_forcing_num_upper_bound_achievable_min_forcing_num_of_isEmpty] rfl
False.elim- Principle of explosion: from False, any proposition follows.
IsEmpty.false- Any element of an empty type produces a contradiction (False).
le_rfl- The order relation ≤ is reflexive ($a \le a$).
Set.encard_empty- The extended cardinality of the empty set is 0.
le_antisymm- In a partial order, if $a \le b$ and $b \le a$, then $a = b$.
iInf_le- The infimum of a family is less than or equal to any member of the family ($\inf_j f(j) \le f(i)$).
le_trans- The order relation ≤ is transitive: if $a \le b$ and $b \le c$, then $a \le c$.
bot_le- In an order with a bottom element $\bot$, $\bot \le a$ for all $a$.
inferInstance- Synthesizes an instance of a typeclass from the current context.
Or.inl- The left injection into a disjunction: proves $P \lor Q$ from a proof of $P$.
Fin.elim0- Eliminates an element of the empty type $\text{Fin } 0$.
op_1371_min_forcing_num_upper_bound_achievable_min_forcing_num_of_isEmpty- For any graph on an empty vertex type, its minimum forcing number is 0.
- The theorem is an existential statement verified by a trivial degenerate instance: the empty graph on 0 vertices ($n = 0$) and the $0 \times 0$ zero matrix over $\mathbb{Q}$. All graph-theoretic properties and the product with $P_4$ hold vacuously.
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.
lemma op_1371_min_forcing_num_upper_bound_achievable_min_forcing_num_of_isEmpty {V : Type*} [IsEmpty V] (G : SimpleGraph V) : graph_min_forcing_num G = 0 := by dsimp [graph_min_forcing_num] have hS : graph_is_forcing_matching G ⊥ := by dsimp [graph_is_forcing_matching, SimpleGraph.Subgraph.IsMatching, SimpleGraph.Subgraph.IsPerfectMatching, SimpleGraph.Subgraph.IsSpanning] refine ⟨fun v _ => False.elim (IsEmpty.false v), ?_⟩ refine ⟨⊥, ⟨⟨fun v _ => False.elim (IsEmpty.false v), fun v => False.elim (IsEmpty.false v)⟩, le_rfl⟩, ?_⟩ rintro M ⟨⟨_, _⟩, _⟩ ext v · exact False.elim (IsEmpty.false v) · exact False.elim (IsEmpty.false v) have he : (⊥ : G.Subgraph).edgeSet.encard = 0 := by rw [show (⊥ : G.Subgraph).edgeSet = ∅ by ext e rcases e with ⟨u, v⟩ exact False.elim (IsEmpty.false u)] exact Set.encard_empty apply le_antisymm · have hle : (⨅ S, ⨅ (_ : graph_is_forcing_matching G S), S.edgeSet.encard) ≤ ⨅ (_ : graph_is_forcing_matching G ⊥), (⊥ : G.Subgraph).edgeSet.encard := iInf_le _ ⊥ have hle2 : (⨅ (_ : graph_is_forcing_matching G ⊥), (⊥ : G.Subgraph).edgeSet.encard) ≤ (⊥ : G.Subgraph).edgeSet.encard := iInf_le _ hS have hle3 := le_trans hle hle2 rwa [he] at hle3 · exact bot_le/-- Achievability of upper bounds on minimum forcing numbers of products with paths (OP-1371). -/theorem op_1371_min_forcing_num_upper_bound_achievable : ∃ (n : ℕ) (G : SimpleGraph (Fin n)) (F : Type) (_ : Field F), G.IsBipartite ∧ ringChar F ≠ 2 ∧ graph_admits_involutory_weighted_adj_matrix G F ∧ ∃ k : ℕ, (4 ≤ k ∧ Even k ∧ graph_min_forcing_num (G □ SimpleGraph.pathGraph k) = ((n / 2 * (k / 2) : ℕ) : ℕ∞)) ∨ (3 ≤ k ∧ Odd k ∧ graph_min_forcing_num (G □ SimpleGraph.pathGraph k) = ((n * (k - 1) / 4 : ℕ) : ℕ∞) + graph_min_forcing_num G) := by refine ⟨0, ⊥, ℚ, inferInstance, ?_, ?_, ?_, 4, Or.inl ⟨le_rfl, ⟨2, rfl⟩, ?_⟩⟩ · refine ⟨⟨fun x => Fin.elim0 x, fun {u} => Fin.elim0 u⟩⟩ · simp · dsimp [graph_admits_involutory_weighted_adj_matrix] use 0 constructor · intro u; exact Fin.elim0 u · ext i; exact Fin.elim0 i · rw [op_1371_min_forcing_num_upper_bound_achievable_min_forcing_num_of_isEmpty] rfl