AFTD Auto-Formalizing Theoretical Domains

diam_boxProd_completeGraph

theoremverified

For every finite connected graph G on a nonempty vertex set and every integer t ≥ 2, the diameter of the Cartesian product G □ K_t is diam(G) + 1.

Statement

theorem diam_boxProd_completeGraph {V : Type*} [Fintype V] [Nonempty V]
    (G : SimpleGraph V) (hG : G.Connected) (t : ℕ) (ht : 2 ≤ t) :
    (G □ SimpleGraph.completeGraph (Fin t)).diam = G.diam + 1
Source
arXiv:2611.03956 Lemma 2.8
Verified
05 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Used by 1

Read back from the Lean

For any finite, nonempty type V, any connected simple graph G on V, and any natural number t with 2 ≤ t, the diameter of the Cartesian product (box product □) of G and the complete graph on Fin t is equal to the diameter of G plus 1.

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 diameter of the Cartesian product G □ K_t is computed by first showing that the extended diameter of any Cartesian product G □ H equals G.ediam + H.ediam, using the additivity of distances in Cartesian products and the distributivity of addition over suprema in ℕ∞. For t ≥ 2, the complete graph K_t is nontrivial, so its extended diameter is 1. Since G is finite and connected, both extended diameters are finite, allowing the conversion from extended diameter in ℕ∞ to standard diameter in ℕ to distribute over addition, which yields diam(G □ K_t) = diam(G) + 1.

  1. For any nonempty graphs G and H, the extended diameter of their Cartesian product is the sum of their extended diameters: (G □ H).ediam = G.ediam + H.ediam.

    Express the extended diameter as the iterated supremum of extended distances over all pairs of vertices. Since the extended distance in G □ H is the sum of the distances in G and H, the extended diameter of G □ H is the supremum of G.edist u v + H.edist x y over all u, v, x, y. Because addition in ℕ∞ distributes over nonempty suprema, this iterated supremum separates into the sum of the supremum for G and the supremum for H, after swapping the order of the suprema.

    lines 4–8

    uses SimpleGraph.ediam_eq_iSup_iSup_edist, SimpleGraph.edist_boxProd, iSup_prod, ENat.iSup_add, ENat.add_iSup, iSup_comm

      simp_rw [SimpleGraph.ediam_eq_iSup_iSup_edist, SimpleGraph.edist_boxProd, iSup_prod]
      rw [ENat.iSup_add]
      simp_rw [ENat.iSup_add, ENat.add_iSup]
      congr 1; ext a₁
      rw [iSup_comm]
  2. The vertex set Fin t is nontrivial and nonempty.

    Because 2 ≤ t, the type Fin t has at least two elements and is therefore nontrivial by Fin.nontrivial_iff_two_le.mpr. Furthermore, 2 ≤ t implies 0 < t by linear integer arithmetic, so Fin t is nonempty by Fin.pos_iff_nonempty.mp.

    lines 14–15

    uses Fin.nontrivial_iff_two_le.mpr, Fin.pos_iff_nonempty.mp

      have h_nontriv : Nontrivial (Fin t) := Fin.nontrivial_iff_two_le.mpr ht
      have h_nonempty : Nonempty (Fin t) := Fin.pos_iff_nonempty.mp (by omega)
  3. The extended diameter of the complete graph on Fin t is 1.

    The complete graph on Fin t is the top element ⊤ in the lattice of simple graphs on Fin t. Because Fin t is nontrivial, the extended diameter of ⊤ is 1 by SimpleGraph.ediam_top.

    lines 16–18

    uses SimpleGraph.ediam_top

      have h_ediam_top : (SimpleGraph.completeGraph (Fin t)).ediam = 1 := by
        change (⊤ : SimpleGraph (Fin t)).ediam = 1
        exact SimpleGraph.ediam_top
  4. Both G and K_t have finite extended diameters (strictly less than ⊤).

    Since G is a nonempty finite connected graph, its extended diameter is not ⊤ by G.connected_iff_ediam_ne_top.mp. The extended diameter of K_t is 1, which is not ⊤ by direct evaluation.

    lines 19–22

    uses G.connected_iff_ediam_ne_top.mp

      have hG_ne_top : G.ediam ≠ ⊤ := G.connected_iff_ediam_ne_top.mp hG
      have hH_ne_top : (SimpleGraph.completeGraph (Fin t)).ediam ≠ ⊤ := by
        rw [h_ediam_top]
        decide
  5. The diameter of the Cartesian product G □ K_t is diam(G) + 1.

    Unfolding the definition of diam, which is the projection of the extended diameter from ℕ∞ to ℕ, the extended diameter of the Cartesian product splits into G.ediam + (K_t).ediam by diam_boxProd_completeGraph_ediam_boxProd. Because both extended diameters are finite, the projection distributes over the sum via ENat.toNat_add. Finally, substituting (K_t).ediam = 1 gives G.diam + 1.

    lines 23–27

    uses diam_boxProd_completeGraph_ediam_boxProd, ENat.toNat_add

      unfold SimpleGraph.diam
      rw [diam_boxProd_completeGraph_ediam_boxProd]
      rw [ENat.toNat_add hG_ne_top hH_ne_top]
      rw [h_ediam_top]
      rfl
SimpleGraph.ediam_eq_iSup_iSup_edist
The extended diameter of a graph is the supremum over all pairs of vertices of the extended distance between them.
SimpleGraph.edist_boxProd
The extended distance between two vertices (u₁, v₁) and (u₂, v₂) in the Cartesian product G □ H is the sum of the extended distance in G and the extended distance in H.
iSup_prod
The supremum of a function over a Cartesian product of two types equals the iterated supremum over each component.
ENat.iSup_add
Over a nonempty index type, adding a constant on the right distributes over the supremum in ℕ∞.
ENat.add_iSup
Over a nonempty index type, adding a constant on the left distributes over the supremum in ℕ∞.
iSup_comm
Two suprema over independent index types can be exchanged.
Fin.nontrivial_iff_two_le.mpr
If 2 ≤ n, then the type Fin n has at least two distinct elements (is nontrivial).
Fin.pos_iff_nonempty.mp
If 0 < n, then Fin n has at least one element (is nonempty).
SimpleGraph.ediam_top
The extended diameter of the complete graph on a nontrivial vertex set is 1.
G.connected_iff_ediam_ne_top.mp
If a nonempty finite graph is connected, its extended diameter is finite (not equal to ⊤).
diam_boxProd_completeGraph_ediam_boxProd
The extended diameter of the Cartesian product of two nonempty graphs is the sum of their extended diameters.
ENat.toNat_add
For extended natural numbers m and n that are not ⊤, the natural number projection of m + n is the sum of their individual projections.

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 diam_boxProd_completeGraph_ediam_boxProd {α β : Type*} [Nonempty α] [Nonempty β]    (G : SimpleGraph α) (H : SimpleGraph β) :    (G □ H).ediam = G.ediam + H.ediam := by  simp_rw [SimpleGraph.ediam_eq_iSup_iSup_edist, SimpleGraph.edist_boxProd, iSup_prod]  rw [ENat.iSup_add]  simp_rw [ENat.iSup_add, ENat.add_iSup]  congr 1; ext a₁  rw [iSup_comm]/-- The diameter of the Cartesian product of a connected graph with K_t (t ≥ 2) is diam(G) + 1. -/theorem diam_boxProd_completeGraph {V : Type*} [Fintype V] [Nonempty V]    (G : SimpleGraph V) (hG : G.Connected) (t : ℕ) (ht : 2 ≤ t) :    (G □ SimpleGraph.completeGraph (Fin t)).diam = G.diam + 1 := by  have h_nontriv : Nontrivial (Fin t) := Fin.nontrivial_iff_two_le.mpr ht  have h_nonempty : Nonempty (Fin t) := Fin.pos_iff_nonempty.mp (by omega)  have h_ediam_top : (SimpleGraph.completeGraph (Fin t)).ediam = 1 := by    change (⊤ : SimpleGraph (Fin t)).ediam = 1    exact SimpleGraph.ediam_top  have hG_ne_top : G.ediam ≠ ⊤ := G.connected_iff_ediam_ne_top.mp hG  have hH_ne_top : (SimpleGraph.completeGraph (Fin t)).ediam ≠ ⊤ := by    rw [h_ediam_top]    decide  unfold SimpleGraph.diam  rw [diam_boxProd_completeGraph_ediam_boxProd]  rw [ENat.toNat_add hG_ne_top hH_ne_top]  rw [h_ediam_top]  rfl
See it in the graphDiscuss this resultChallenge it