AFTD Auto-Formalizing Theoretical Domains

op_258_no_mono_triangle_of_layering

theoremverified

If an edge colouring c of K_n is subordinate to a bipartite edge layering (so each colour lives in a layer whose endpoints have distinct values under a 2-colouring), then c contains no monochromatic triangle K_3.

Statement

theorem op_258_no_mono_triangle_of_layering (n : ℕ) (l : ℕ)
    (layer : (SimpleGraph.completeGraph (Fin n)).edgeSet → Fin l)
    (f : Fin l → Fin n → Fin 2)
    (h_bip : ∀ (u v : Fin n) (hne : u ≠ v),
      f (layer ⟨s(u, v), by simp [SimpleGraph.completeGraph_eq_top, hne]⟩) u ≠
      f (layer ⟨s(u, v), by simp [SimpleGraph.completeGraph_eq_top, hne]⟩) v)
    (c : (SimpleGraph.completeGraph (Fin n)).edgeSet → ℕ+)
    (col_layer : ℕ+ → Fin l)
    (hc_layer : ∀ e, col_layer (c e) = layer e) :
    ¬ op_258_has_mono_clique n c 3
Source
step towards op_258_sum_ne_top_of_forces_three
Verified
22 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1
  • op_258_has_mono_cliqueThe colouring c of the edges of K_n has a monochromatic K_k: there are a k-element vertex set s and a colour i such that every edge inside…
Used by 1
  • op_258_sum_ne_top_of_forces_threeIf a positive antitone profile a forces a monochromatic triangle K_3 on sufficiently large complete graphs, then the infinite sum of a_i…

The proof, explained

The proof proceeds by contradiction. Suppose there exists a monochromatic triangle, that is, a 3-element set of vertices $s$ whose edges all have colour $i$. Since colour $i$ is subordinate to a single bipartite layer, every edge in the triangle connects vertices with different values under that layer's 2-colouring. This forces the 2-colouring function to be injective on the 3 vertices of $s$, implying $|s| \le 2$, which contradicts $|s| = 3$.

  1. For any distinct vertices u and v, the unordered pair {u, v} is an edge of the complete graph K_n.

    In the theorem signature, specifying the edge passed to `layer` in hypothesis `h_bip` requires proof that $s(u, v)$ belongs to the edge set of $K_n$. Simplifying with `SimpleGraph.completeGraph_eq_top` and the assumption $u \neq v$ discharges this requirement for both endpoints.

    lines 6–7

    uses SimpleGraph.completeGraph_eq_top

          f (layer ⟨s(u, v), by simp [SimpleGraph.completeGraph_eq_top, hne]⟩) u ≠
          f (layer ⟨s(u, v), by simp [SimpleGraph.completeGraph_eq_top, hne]⟩) v)
  2. Suppose, for contradiction, that there is a monochromatic triangle: a set s of 3 vertices such that all edges between distinct vertices in s have the same colour i.

    We assume for contradiction that `op_258_has_mono_clique n c 3` holds. Deconstructing this assumption gives a subset of vertices $s \subseteq \operatorname{Fin} n$ with $|s| = 3$ and a colour $i \in \mathbb{N}^+$ such that every edge between distinct vertices of $s$ has colour $i$.

    line 12

      rintro ⟨s, i, hcard, hmono⟩
  3. For any two distinct vertices in s, their values under the 2-colouring of layer col_layer(i) must be distinct.

    Let $u, v \in s$ be distinct vertices. By the monochromatic assumption, the edge between them has colour $i$. Since colour $i$ is assigned to layer $\operatorname{col\_layer}(i)$ (via hypothesis `hc_layer`), this edge belongs to that layer. The bipartiteness hypothesis `h_bip` states that any edge in a layer connects vertices with different 2-colouring values in that layer, so $f(\operatorname{col\_layer}(i))(u) \neq f(\operatorname{col\_layer}(i))(v)$.

    lines 13–19

    uses SimpleGraph.completeGraph_eq_top

      have key : ∀ (u v : Fin n) (hu : u ∈ s) (hv : v ∈ s) (hne : u ≠ v),
          f (col_layer i) u ≠ f (col_layer i) v := by
        intro u v hu hv hne
        have hcv : c ⟨s(u,v), by simp [SimpleGraph.completeGraph_eq_top, hne]⟩ = i := hmono hu hv hne
        have hl : layer ⟨s(u,v), by simp [SimpleGraph.completeGraph_eq_top, hne]⟩ = col_layer i := by
          rw [← hc_layer ⟨s(u,v), by simp [SimpleGraph.completeGraph_eq_top, hne]⟩, hcv]
        simpa [hl] using h_bip u v hne
  4. The restriction of the 2-colouring f(col_layer(i)) to s is an injective function from s to Fin 2.

    If two vertices $x, y \in s$ had the same value under $f(\operatorname{col\_layer}(i))$, they could not be distinct by the previous claim (`key`), so $x = y$ (using `Subtype.ext` to lift the equality of underlying vertices).

    lines 20–23

    uses Subtype.ext

      have hinj : Function.Injective (fun x : s => f (col_layer i) (x : Fin n)) := by
        intro x y hxy
        by_contra hne
        exact key (x : Fin n) (y : Fin n) x.property y.property (fun h => hne (Subtype.ext h)) hxy
  5. The cardinality of s is at most 2.

    By `Fintype.card_le_of_injective`, the existence of an injective map from $s$ to $\operatorname{Fin} 2$ implies that $|s| \le |\operatorname{Fin} 2|$. Simplifying the cardinalities via `Fintype.card_coe` and `Fintype.card_fin` gives $|s| \le 2$.

    lines 24–25

    uses Fintype.card_le_of_injective, Fintype.card_coe, Fintype.card_fin

      have hle := Fintype.card_le_of_injective (fun x : s => f (col_layer i) (x : Fin n)) hinj
      simp only [Fintype.card_coe, Fintype.card_fin] at hle
  6. False (a contradiction is derived).

    Linear integer arithmetic (`omega`) detects the contradiction between the assumption $|s| = 3$ and the derived inequality $|s| \le 2$.

    line 26

      omega
SimpleGraph.completeGraph_eq_top
In a complete graph, every pair of distinct vertices forms an edge.
Subtype.ext
Two elements of a subtype are equal if and only if their underlying values are equal.
Fintype.card_le_of_injective
If an injective function exists between two finite types, the cardinality of the domain is at most the cardinality of the codomain.
Fintype.card_coe
The cardinality of a subtype induced by a finite set equals the cardinality of the finite set itself.
Fintype.card_fin
The cardinality of the standard finite type Fin n is n.

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

/-- An edge colouring subordinate to a family of bipartite layers has no monochromatic K_3. -/theorem op_258_no_mono_triangle_of_layering (n : ℕ) (l : ℕ)    (layer : (SimpleGraph.completeGraph (Fin n)).edgeSet → Fin l)    (f : Fin l → Fin n → Fin 2)    (h_bip : ∀ (u v : Fin n) (hne : u ≠ v),      f (layer ⟨s(u, v), by simp [SimpleGraph.completeGraph_eq_top, hne]⟩) u ≠      f (layer ⟨s(u, v), by simp [SimpleGraph.completeGraph_eq_top, hne]⟩) v)    (c : (SimpleGraph.completeGraph (Fin n)).edgeSet → ℕ+)    (col_layer : ℕ+ → Fin l)    (hc_layer : ∀ e, col_layer (c e) = layer e) :    ¬ op_258_has_mono_clique n c 3 := by  rintro ⟨s, i, hcard, hmono⟩  have key : ∀ (u v : Fin n) (hu : u ∈ s) (hv : v ∈ s) (hne : u ≠ v),      f (col_layer i) u ≠ f (col_layer i) v := by    intro u v hu hv hne    have hcv : c ⟨s(u,v), by simp [SimpleGraph.completeGraph_eq_top, hne]⟩ = i := hmono hu hv hne    have hl : layer ⟨s(u,v), by simp [SimpleGraph.completeGraph_eq_top, hne]⟩ = col_layer i := by      rw [← hc_layer ⟨s(u,v), by simp [SimpleGraph.completeGraph_eq_top, hne]⟩, hcv]    simpa [hl] using h_bip u v hne  have hinj : Function.Injective (fun x : s => f (col_layer i) (x : Fin n)) := by    intro x y hxy    by_contra hne    exact key (x : Fin n) (y : Fin n) x.property y.property (fun h => hne (Subtype.ext h)) hxy  have hle := Fintype.card_le_of_injective (fun x : s => f (col_layer i) (x : Fin n)) hinj  simp only [Fintype.card_coe, Fintype.card_fin] at hle  omega
See it in the graphDiscuss this resultChallenge it