simple_graph_is_seal_free_partition_one_block
If G is a connected graph with edge colouring γ, then the one-block vertex map (everything ↦ 0) is a seal-free partition.
Statement
theorem simple_graph_is_seal_free_partition_one_block {V α : Type*} (G : SimpleGraph V) (γ : G.edgeSet → α) (hG : G.Connected) : simple_graph_is_seal_free_partition G γ 1 (fun _ => 0)
- Source
- step towards quadripartite_minimum_coloring_max_wild_number_eq
- Verified
- 01 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- simple_graph_is_seal_free_partitionA vertex map p : V → Fin q is a seal-free block partition for an edge colouring γ of a graph G when (i) every block {v | p v = i} induces…
The proof, explained
The definition of a seal-free partition requires each block to induce a connected subgraph and every non-empty proper subset of blocks to admit boundary edges of every colour. When partitioning into a single block (q = 1), the unique block comprises the entire vertex set, so its induced subgraph is isomorphic to the original connected graph G. Furthermore, the index set Fin 1 has no non-empty proper subsets, making the boundary edge condition vacuously true.
To show that the constant partition is seal-free, it suffices to verify that the single block induces a connected subgraph and that the boundary condition holds for all non-empty proper subsets of blocks.
Unfolding the definition simple_graph_is_seal_free_partition reveals two conjuncts: first, that every block index i ∈ Fin 1 induces a connected subgraph; second, that for every edge and every non-empty proper subset T ⊊ Fin 1, there exists a cross-boundary edge with the same colour.
uses
simple_graph_is_seal_free_partitiondsimp [simple_graph_is_seal_free_partition] refine ⟨fun i => ?_, fun e T hT_nonempty hT_ne_univ => ?_⟩
For any index i ∈ Fin 1, the block {v ∈ V | 0 = i} equals the entire vertex set V.
Because Fin 1 has a unique element, any two elements are equal by Subsingleton.elim, so 0 = i is trivially satisfied for all vertices v. Thus the fiber of the partition map is all of V (Set.univ).
uses
Subsingleton.elim· have hs : {v : V | (fun _ => (0 : Fin 1)) v = i} = (Set.univ : Set V) := by ext v simp [Subsingleton.elim ((fun _ => (0 : Fin 1)) v) i]
The induced subgraph on the single block is connected.
Rewriting the block vertex set to Set.univ, the induced subgraph is isomorphic to G via SimpleGraph.induceUnivIso. Since graph isomorphisms preserve connectedness and G is connected by hypothesis (hG), the induced subgraph is connected.
uses
SimpleGraph.induceUnivIsorw [hs] exact (SimpleGraph.induceUnivIso G).connected_iff.mpr hG
Any non-empty subset T ⊆ Fin 1 is the universal set Finset.univ.
Since T is non-empty, it contains some element x. Any element y ∈ Fin 1 equals x by Subsingleton.elim, so y must also belong to T. Hence T contains every element of Fin 1, establishing T = Finset.univ.
uses
Subsingleton.elim,Finset.mem_univ,iff_true· obtain ⟨x, hx⟩ := hT_nonempty have hT_univ : T = Finset.univ := by ext y simp only [Finset.mem_univ, iff_true] have : y = x := Subsingleton.elim y x rwa [this]
The boundary condition holds vacuously by contradiction.
The hypothesis hT_ne_univ states that T ≠ Finset.univ, directly contradicting the fact that T = Finset.univ. Applying False.elim closes the goal.
uses
False.elimexact False.elim (hT_ne_univ hT_univ)
simple_graph_is_seal_free_partition- A partition p of the vertices of a graph G into q blocks is seal-free with respect to edge colouring γ if each block induces a connected subgraph, and every non-empty proper subset of blocks has a boundary edge of each edge colour.
Subsingleton.elim- In any type with at most one element (a subsingleton), any two elements are equal.
SimpleGraph.induceUnivIso- The subgraph of a graph G induced on the entire vertex set Set.univ is isomorphic to G.
Finset.mem_univ- Every element of a finite type belongs to the universal finset.
iff_true- A proposition p is equivalent to True if and only if p holds.
False.elim- From a false hypothesis (a contradiction), any proposition can be deduced.
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.
/-- A connected graph always admits a seal-free partition into one block, so the definition is satisfiable. -/theorem simple_graph_is_seal_free_partition_one_block {V α : Type*} (G : SimpleGraph V) (γ : G.edgeSet → α) (hG : G.Connected) : simple_graph_is_seal_free_partition G γ 1 (fun _ => 0) := by dsimp [simple_graph_is_seal_free_partition] refine ⟨fun i => ?_, fun e T hT_nonempty hT_ne_univ => ?_⟩ · have hs : {v : V | (fun _ => (0 : Fin 1)) v = i} = (Set.univ : Set V) := by ext v simp [Subsingleton.elim ((fun _ => (0 : Fin 1)) v) i] rw [hs] exact (SimpleGraph.induceUnivIso G).connected_iff.mpr hG · obtain ⟨x, hx⟩ := hT_nonempty have hT_univ : T = Finset.univ := by ext y simp only [Finset.mem_univ, iff_true] have : y = x := Subsingleton.elim y x rwa [this] exact False.elim (hT_ne_univ hT_univ)