simple_graph_is_color_connecting_mono
A set of edges containing a colour-connecting set is colour-connecting.
Statement
theorem simple_graph_is_color_connecting_mono {V α : Type*} (G : SimpleGraph V) (γ : G.edgeSet → α) {W W' : Set (Sym2 V)} (hW : simple_graph_is_color_connecting G γ W) (hWW' : W ⊆ W') (hW' : W' ⊆ G.edgeSet) : simple_graph_is_color_connecting G γ W'
- Source
- Sanity lemma for colour-connecting sets, arXiv:2610.22142 (Wild number for spanning trees in complete and complete bipartite graphs), Sec. 2.
- Verified
- 16 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- simple_graph_is_color_connectingLet γ be an edge colouring of a graph G. A set W of edges of G is colour-connecting if, for every colour c used by γ, the spanning…
The proof, explained
To show that any superset $W' \subseteq E(G)$ of a colour-connecting set $W$ is colour-connecting, we verify the two conditions in the definition. The edge inclusion $W' \subseteq E(G)$ is assumed directly. For every edge $e$, the graph formed by the edges of colour $\gamma(e)$ together with $W'$ is a supergraph of the corresponding connected graph for $W$, and adding edges preserves connectedness.
The edge set $W'$ is colour-connecting for $G$ and $\gamma$.
By definition, $W'$ is colour-connecting if $W' \subseteq E(G)$ and for every edge $e$, the graph formed by all edges sharing the colour of $e$ together with $W'$ is connected. The first condition holds directly by hypothesis $hW'$. For the second condition, for any edge $e$, the set of edges of colour $\gamma(e)$ union $W$ is contained in the set of edges of colour $\gamma(e)$ union $W'$ by `Set.union_subset_union_right` since $W \subseteq W'$ ($hWW'$). By `SimpleGraph.fromEdgeSet_mono`, this inclusion induces a subgraph relation, and because adding edges preserves connectedness (monotonicity of connectedness), the connected graph for $W$ implies the graph for $W'$ is also connected.
uses
SimpleGraph.fromEdgeSet_mono,Set.union_subset_union_right⟨hW', fun e => (hW.2 e).mono (SimpleGraph.fromEdgeSet_mono (Set.union_subset_union_right _ hWW'))⟩
SimpleGraph.fromEdgeSet_mono- If a set of edges $s$ is a subset of $t$, then the simple graph generated by $s$ is a subgraph of the simple graph generated by $t$.
Set.union_subset_union_right- Taking the union with a fixed set on the left preserves set inclusion: if $t_1 \subseteq t_2$, then $s \cup t_1 \subseteq s \cup t_2$.
Written by a model (gemini-3.8-flash) from the Lean source alone (no goal states were available). Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
theorem simple_graph_is_color_connecting_mono {V α : Type*} (G : SimpleGraph V) (γ : G.edgeSet → α) {W W' : Set (Sym2 V)} (hW : simple_graph_is_color_connecting G γ W) (hWW' : W ⊆ W') (hW' : W' ⊆ G.edgeSet) : simple_graph_is_color_connecting G γ W' := ⟨hW', fun e => (hW.2 e).mono (SimpleGraph.fromEdgeSet_mono (Set.union_subset_union_right _ hWW'))⟩