AFTD Auto-Formalizing Theoretical Domains

mono_color_subgraph_le

theoremverified

The monochromatic subgraph of G in colour col is a subgraph of G.

Statement

theorem mono_color_subgraph_le {V C : Type*} (G : SimpleGraph V) (c : G.edgeSet → C) (col : C) :
    mono_color_subgraph G c col ≤ G
Source
arXiv:2610.29813
Verified
23 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1
  • mono_color_subgraphFor a simple graph G and an edge colouring c with colours in C, the monochromatic subgraph mono_color_subgraph G c col is the spanning…

Read back from the Lean

For any types V and C, any simple graph G on V, any coloring of the edges of G by C (a function c : G.edgeSet → C), and any color col : C, the monochromatic subgraph mono_color_subgraph G c col is less than or equal to G in the subgraph ordering on SimpleGraph V (i.e., it is a subgraph of G).

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

To prove that the monochromatic subgraph of $G$ is a subgraph of $G$, we show that adjacency in the monochromatic subgraph implies adjacency in $G$. Unfolding the construction of the monochromatic subgraph reveals that every such edge comes with a witness that it belongs to the edge set of $G$. Providing this witness finishes the proof.

  1. To prove the subgraph inclusion, it suffices to show that any two vertices adjacent in the monochromatic subgraph are adjacent in $G$.

    By definition of the subgraph ordering ($\le$) on simple graphs, a graph is a subgraph of $G$ if its adjacency relation implies adjacency in $G$. We introduce arbitrary vertices $u, v \in V$ and the hypothesis $h$ that they are adjacent in the monochromatic subgraph.

    line 4

      intro u v h
  2. The hypothesis $h$ states that the unordered pair $\{u, v\}$ belongs to the set of edges of $G$ having color `col`, with $u \neq v$.

    We unfold the definition of `mono_color_subgraph` and rewrite with `SimpleGraph.fromEdgeSet_adj`, transforming $h$ into the conjunction that the edge $s(u, v) \in \{e \mid \exists (h : e \in G.\text{edgeSet}), c \langle e, h \rangle = \text{col}\}$ and $u \neq v$.

    line 5

    uses mono_color_subgraph, SimpleGraph.fromEdgeSet_adj

      rw [mono_color_subgraph, SimpleGraph.fromEdgeSet_adj] at h
  3. The vertices $u$ and $v$ are adjacent in $G$.

    From the first component of $h$, we extract the witness `hedge` establishing that $s(u, v) \in G.\text{edgeSet}$ (ignoring the specific color equality). Because belonging to the edge set of $G$ is definitionally adjacency in $G$, this witness completes the proof.

    lines 6–7

      obtain ⟨hedge, -⟩ := h.1
      exact hedge
SimpleGraph.fromEdgeSet_adj
Two vertices $v$ and $w$ are adjacent in the simple graph constructed from edge set $s$ if and only if the unordered pair $\{v, w\} \in s$ and $v \neq w$.
mono_color_subgraph
The simple graph on vertex type $V$ whose edges are the edges of $G$ assigned color `col` by coloring $c$.

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

/-- Every monochromatic subgraph of G is a subgraph of G. -/theorem mono_color_subgraph_le {V C : Type*} (G : SimpleGraph V) (c : G.edgeSet → C) (col : C) :    mono_color_subgraph G c col ≤ G := by  intro u v h  rw [mono_color_subgraph, SimpleGraph.fromEdgeSet_adj] at h  obtain ⟨hedge, -⟩ := h.1  exact hedge
See it in the graphDiscuss this resultChallenge it