diam_boxProd_completeGraph
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
- exists_connected_all_powers_well_covered_diam_geFor every positive integer D, there exists a finite connected simple graph G with diameter at least D such that every positive power G^d…
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.
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.
uses
SimpleGraph.ediam_eq_iSup_iSup_edist,SimpleGraph.edist_boxProd,iSup_prod,ENat.iSup_add,ENat.add_iSup,iSup_commsimp_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 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.
uses
Fin.nontrivial_iff_two_le.mpr,Fin.pos_iff_nonempty.mphave 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)
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.
uses
SimpleGraph.ediam_tophave h_ediam_top : (SimpleGraph.completeGraph (Fin t)).ediam = 1 := by change (⊤ : SimpleGraph (Fin t)).ediam = 1 exact SimpleGraph.ediam_top
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.
uses
G.connected_iff_ediam_ne_top.mphave 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
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.
uses
diam_boxProd_completeGraph_ediam_boxProd,ENat.toNat_addunfold 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.
- The standard diameter `diam` in Mathlib is defined by projecting the extended diameter `ediam : ℕ∞` into `ℕ` using `ENat.toNat`. Consequently, the proof first calculates the extended diameter of the Cartesian product and then casts to `ℕ`.
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 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