mono_color_subgraph_le
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.
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.
intro u v hThe 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$.
uses
mono_color_subgraph,SimpleGraph.fromEdgeSet_adjrw [mono_color_subgraph, SimpleGraph.fromEdgeSet_adj] at h
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.
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
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.
/-- 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