AFTD Auto-Formalizing Theoretical Domains

op_1371_min_forcing_num_upper_bound_achievable

theoremverifiedformalization

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

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.

  1. 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$.

    lines 4–12

    uses False.elim, IsEmpty.false, le_rfl

      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)
  2. 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.

    lines 13–18

    uses False.elim, IsEmpty.false, Set.encard_empty

      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
  3. 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.

    lines 19–28

    uses le_antisymm, iInf_le, le_trans, bot_le

      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
  4. 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.

    line 40

    uses inferInstance, Or.inl, le_rfl

      refine ⟨0, ⊥, ℚ, inferInstance, ?_, ?_, ?_, 4, Or.inl ⟨le_rfl, ⟨2, rfl⟩, ?_⟩⟩
  5. 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`).

    line 41

    uses Fin.elim0

      · refine ⟨⟨fun x => Fin.elim0 x, fun {u} => Fin.elim0 u⟩⟩
  6. 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.

    line 42

      · simp
  7. The 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.

    lines 43–47

    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
  8. 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.

    lines 48–49

    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.

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

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
See it in the graphDiscuss this resultChallenge it