AFTD Auto-Formalizing Theoretical Domains

simple_graph_is_seal_free_partition_one_block

theoremverified

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.

  1. 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.

    lines 5–6

    uses simple_graph_is_seal_free_partition

      dsimp [simple_graph_is_seal_free_partition]
      refine ⟨fun i => ?_, fun e T hT_nonempty hT_ne_univ => ?_⟩
  2. 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).

    lines 7–9

    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]
  3. 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.

    lines 10–11

    uses SimpleGraph.induceUnivIso

        rw [hs]
        exact (SimpleGraph.induceUnivIso G).connected_iff.mpr hG
  4. 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.

    lines 12–17

    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]
  5. 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.

    line 18

    uses False.elim

        exact 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

/-- 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)
See it in the graphDiscuss this resultChallenge it