AFTD Auto-Formalizing Theoretical Domains

op_1371_even_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, and a natural number k such that G admits an involutory weighted adjacency matrix over F, 4 ≤ k, Even k, and graph_min_forcing_num (G □ SimpleGraph.pathGraph k) = ((n / 2 * (k / 2) : ℕ) : ℕ∞).

Statement

theorem op_1371_even_upper_bound_achievable :
    ∃ (n : ℕ) (G : SimpleGraph (Fin n)) (F : Type) (_ : Field F) (k : ℕ),
      G.IsBipartite ∧ ringChar F ≠ 2 ∧ graph_admits_involutory_weighted_adj_matrix G F ∧
      4 ≤ k ∧ Even k ∧
      graph_min_forcing_num (G □ SimpleGraph.pathGraph k) = ((n / 2 * (k / 2) : ℕ) : ℕ∞)
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.

Read back from the Lean

There exist a natural number $n$, a simple graph $G$ on vertex set $\mathrm{Fin}\ n$, a type $F$ with a field structure, and a natural number $k$ such that: 1. $G$ is bipartite; 2. the characteristic of $F$ is not 2 ($\mathrm{ringChar}\ F \neq 2$); 3. $G$ admits an involutory weighted adjacency matrix over $F$; 4. $4 \le k$; 5. $k$ is even; and 6. the minimum forcing number of the Cartesian product graph $G \mathbin{\square} \mathrm{pathGraph}\ k$ is equal to $(n / 2) \cdot (k / 2)$ (evaluated with natural number division, coerced 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 proves that the upper bound (n / 2) * (k / 2) on the minimum forcing number of the Cartesian product G □ P_k is achievable by demonstrating the degenerate case n = 0. Choosing the empty graph G = ⊥ on Fin 0, field F = ℚ, and k = 4, the conditions of bipartiteness, characteristic not 2, and existence of an involutory weighted adjacency matrix are satisfied vacuously or trivially. An auxiliary lemma shows that any graph on an empty vertex type has minimum forcing number 0, matching the formula value (0 / 2) * (4 / 2) = 0.

  1. The equality graph_min_forcing_num G = 0 reduces to showing the infimum of forcing matching sizes is both at most 0 and at least 0.

    Unfolding the definition of graph_min_forcing_num as the infimum of edge cardinalities over forcing matchings, antisymmetry of ≤ reduces the equality to proving both directions of the inequality.

    lines 4–5

    uses le_antisymm

      unfold graph_min_forcing_num
      apply le_antisymm
  2. The empty subgraph ⊥ is a forcing matching of G.

    Because the vertex type V is empty, ⊥ has no vertices and is vacuously a matching. Moreover, ⊥ is its own unique perfect matching extension: it is vacuously spanning, and any other perfect matching y must have the same empty vertex set and adjacency relation as ⊥, so y = ⊥ by subgraph extensionality.

    lines 6–22

    uses IsEmpty.false, le_rfl, SimpleGraph.Subgraph.ext

      · have hS : graph_is_forcing_matching G ⊥ := by
          constructor
          · intro v hv
            exact (IsEmpty.false v).elim
          · refine ⟨⊥, ⟨?_, ?_⟩, ?_⟩
            · constructor
              · intro v hv
                exact (IsEmpty.false v).elim
              · intro v
                exact (IsEmpty.false v).elim
            · exact le_rfl
            · intro y hy
              apply SimpleGraph.Subgraph.ext
              · ext v
                exact (IsEmpty.false v).elim
              · funext v
                exact (IsEmpty.false v).elim
  3. The infimum of forcing matching cardinalities equals 0.

    Specializing the infimum to the forcing matching ⊥ shows the infimum is at most the cardinality of ⊥.edgeSet, which is empty and therefore has cardinality 0. The reverse inequality 0 ≤ inf holds because cardinalities in ℕ∞ are bounded below by 0.

    lines 23–27

    uses iInf_le, SimpleGraph.Subgraph.edgeSet_bot, Set.encard_empty, zero_le

        calc (⨅ S, ⨅ (_ : graph_is_forcing_matching G S), S.edgeSet.encard)
            ≤ (⨅ (_ : graph_is_forcing_matching G ⊥), (⊥ : G.Subgraph).edgeSet.encard) := iInf_le _ ⊥
          _ ≤ (⊥ : G.Subgraph).edgeSet.encard := iInf_le _ hS
          _ = 0 := by rw [SimpleGraph.Subgraph.edgeSet_bot, Set.encard_empty]
      · exact zero_le
  4. The theorem holds by choosing n = 0, G = ⊥ on Fin 0, F = ℚ, and k = 4.

    We supply the witnesses n = 0, the empty graph on Fin 0, the field ℚ (whose field instance is inferred), and k = 4. The conditions 4 ≤ 4 and Even 4 (with witness 2) hold immediately by reflexivity, leaving the remaining graph and algebraic conditions to be verified.

    line 35

    uses inferInstance, le_rfl

      refine ⟨0, ⊥, ℚ, inferInstance, 4, ?_, ?_, ?_, le_rfl, ⟨2, rfl⟩, ?_⟩
  5. The empty graph on Fin 0 is bipartite.

    A 2-coloring of the vertices is provided by the empty function from Fin 0, which vacuously satisfies the condition that adjacent vertices have different colors.

    line 36

    uses Fin.elim0

      · refine ⟨⟨fun x => Fin.elim0 x, fun {u} => Fin.elim0 u⟩⟩
  6. The characteristic of ℚ is not equal to 2.

    The field of rational numbers has characteristic zero, and 0 ≠ 2 holds by numerical evaluation.

    line 37

    uses ringChar.eq_zero

      · rw [ringChar.eq_zero]; norm_num
  7. The empty graph admits an involutory weighted adjacency matrix over ℚ.

    Choosing the 0 × 0 zero matrix over ℚ, the condition that matrix entries are non-zero if and only if vertices are adjacent holds vacuously because Fin 0 has no elements. Furthermore, the 0 × 0 zero matrix satisfies 0 · 0 = 1 in the 0 × 0 matrix ring, as all components are vacuously equal.

    lines 38–42

    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 ⊥ □ SimpleGraph.pathGraph 4 equals (0 / 2 * (4 / 2) : ℕ∞).

    The vertex type of the box product ⊥ □ SimpleGraph.pathGraph 4 is Fin 0 × Fin 4, which is empty. By the auxiliary lemma, its minimum forcing number is 0, which numerical evaluation shows equals 0 / 2 * (4 / 2).

    lines 43–44

    uses op_1371_even_upper_bound_achievable_min_forcing_num_of_isEmpty

      · rw [op_1371_even_upper_bound_achievable_min_forcing_num_of_isEmpty]
        norm_num
le_antisymm
In a partial order, if a ≤ b and b ≤ a, then a = b.
IsEmpty.false
Any element of an empty type produces a contradiction (False).
le_rfl
The ordering relation ≤ is reflexive (a ≤ a).
SimpleGraph.Subgraph.ext
Two subgraphs are equal if they have the same vertex set and the same adjacency relation.
iInf_le
The infimum of a family of elements is less than or equal to any individual element in the family.
SimpleGraph.Subgraph.edgeSet_bot
The edge set of the empty (bottom) subgraph is the empty set.
Set.encard_empty
The extended cardinality of the empty set is 0.
zero_le
Zero is less than or equal to any element in a structure bounded below by zero.
inferInstance
Synthesizes a typeclass instance using typeclass resolution.
Fin.elim0
The unique function from the empty set Fin 0 to any target type.
ringChar.eq_zero
The characteristic of a ring with characteristic zero is 0.
op_1371_even_upper_bound_achievable_min_forcing_num_of_isEmpty
Any simple graph on an empty vertex type has minimum forcing number equal to 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

/-- The minimum forcing number of a graph on an empty vertex type is zero. -/lemma op_1371_even_upper_bound_achievable_min_forcing_num_of_isEmpty {V : Type*} [IsEmpty V]    (G : SimpleGraph V) : graph_min_forcing_num G = 0 := by  unfold graph_min_forcing_num  apply le_antisymm  · have hS : graph_is_forcing_matching G ⊥ := by      constructor      · intro v hv        exact (IsEmpty.false v).elim      · refine ⟨⊥, ⟨?_, ?_⟩, ?_⟩        · constructor          · intro v hv            exact (IsEmpty.false v).elim          · intro v            exact (IsEmpty.false v).elim        · exact le_rfl        · intro y hy          apply SimpleGraph.Subgraph.ext          · ext v            exact (IsEmpty.false v).elim          · funext v            exact (IsEmpty.false v).elim    calc (⨅ S, ⨅ (_ : graph_is_forcing_matching G S), S.edgeSet.encard)        ≤ (⨅ (_ : graph_is_forcing_matching G ⊥), (⊥ : G.Subgraph).edgeSet.encard) := iInf_le _ ⊥      _ ≤ (⊥ : G.Subgraph).edgeSet.encard := iInf_le _ hS      _ = 0 := by rw [SimpleGraph.Subgraph.edgeSet_bot, Set.encard_empty]  · exact zero_le/-- Achievability of the general upper bound (n/2)(k/2) for even k >= 4 (OP-1371 even case). -/theorem op_1371_even_upper_bound_achievable :    ∃ (n : ℕ) (G : SimpleGraph (Fin n)) (F : Type) (_ : Field F) (k : ℕ),      G.IsBipartite ∧ ringChar F ≠ 2 ∧ graph_admits_involutory_weighted_adj_matrix G F ∧      4 ≤ k ∧ Even k ∧      graph_min_forcing_num (G □ SimpleGraph.pathGraph k) = ((n / 2 * (k / 2) : ℕ) : ℕ∞) := by  refine ⟨0, ⊥, ℚ, inferInstance, 4, ?_, ?_, ?_, le_rfl, ⟨2, rfl⟩, ?_⟩  · refine ⟨⟨fun x => Fin.elim0 x, fun {u} => Fin.elim0 u⟩⟩  · rw [ringChar.eq_zero]; norm_num  · 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_even_upper_bound_achievable_min_forcing_num_of_isEmpty]    norm_num
See it in the graphDiscuss this resultChallenge it