AFTD Auto-Formalizing Theoretical Domains

not_is_fix_v0_of_isolated

lemmaverified

An isolated vertex v in a finite simple graph G (with empty neighborhood) does not belong to V_fix^0(G).

Statement

lemma not_is_fix_v0_of_isolated {V : Type*} [Fintype V] [DecidableEq V]
    (G : SimpleGraph V) (v : V) (hiso : G.neighborSet v = ∅) :
    ¬ is_fix_v0 G v
Source
arXiv:2610.26912: Theorem 2.22 -- Vertex Removal and Vertex-Edge Domination
Verified
21 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 4
  • is_fix_v0A vertex v of a finite simple graph G belongs to V_fix^0(G) if v is in V^0(G) and v belongs to every minimum vertex-edge dominating set S…
  • is_v0A vertex v of a finite simple graph G belongs to V^0(G) if removing v preserves the vertex-edge domination number, that is, gamma_ve(G -…
  • is_ve_dominatingA subset S of vertices in a simple graph G is a vertex-edge dominating set if for all vertices x and y with G.Adj x y, there exists u in S…
  • gamma_veThe vertex-edge domination number gamma_ve(G) of a finite simple graph G is the minimum cardinality of a finite subset S of V that is a…

Read back from the Lean

For any finite type V with decidable equality, any simple graph G on V, and any vertex v : V, if the neighbor set of v in G is empty (G.neighborSet v = ∅, i.e., v is an isolated vertex), then v is not a "fix $v_0$" vertex of G (¬ is_fix_v0 G v).

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

Lean source view module on GitHub

/-- An isolated vertex cannot belong to V_fix^0(G). -/
lemma not_is_fix_v0_of_isolated {V : Type*} [Fintype V] [DecidableEq V]
    (G : SimpleGraph V) (v : V) (hiso : G.neighborSet v = ∅) :
    ¬ is_fix_v0 G v := by
  intro hfix
  -- Any edge incident to v is impossible.
  have hv_adj : ∀ w, ¬ G.Adj v w := by
    intro w hw
    have h' : w ∈ G.neighborSet v := (SimpleGraph.mem_neighborSet G v w).mpr hw
    rw [hiso] at h'
    exact h'
  -- The full vertex set is vertex-edge dominating, so gamma_ve is attained.
  have huniv : is_ve_dominating G ((Finset.univ : Finset V) : Set V) := by
    intro x y _
    exact ⟨x, Finset.mem_univ x, Or.inl rfl⟩
  have hne : ({k : ℕ | ∃ S : Finset V, is_ve_dominating G (S : Set V) ∧ S.card = k}).Nonempty := by
    exact ⟨Fintype.card V, Finset.univ, huniv, Finset.card_univ⟩
  obtain ⟨S0, hdom0, hcard0⟩ := Nat.sInf_mem hne
  -- Removing the isolated vertex v preserves vertex-edge domination.
  have hdom_erase : is_ve_dominating G ((S0.erase v : Finset V) : Set V) := by
    intro x y hxy
    obtain ⟨u, huS0, hu⟩ := hdom0 hxy
    have hune : u ≠ v := by
      rintro rfl
      rcases hu with h | h | h | h
      · rw [← h] at hxy
        exact hv_adj y hxy
      · exact hv_adj x h
      · rw [← h] at hxy
        exact hv_adj x hxy.symm
      · exact hv_adj y h
    exact ⟨u, Finset.mem_erase.mpr ⟨hune, huS0⟩, hu⟩
  -- Hence S0.erase v is still a minimum vertex-edge dominating set.
  have hcard_erase_mem :
      (S0.erase v).card ∈ ({k : ℕ | ∃ S : Finset V, is_ve_dominating G (S : Set V) ∧ S.card = k}) :=
    ⟨S0.erase v, hdom_erase, rfl⟩
  have hgamma_le : gamma_ve G ≤ (S0.erase v).card := Nat.sInf_le hcard_erase_mem
  have hle1 : (S0.erase v).card ≤ gamma_ve G := by
    calc (S0.erase v).card ≤ S0.card := Finset.card_erase_le
      _ = gamma_ve G := hcard0
  have hcard_erase_eq : (S0.erase v).card = gamma_ve G := le_antisymm hle1 hgamma_le
  -- But is_fix_v0 demands v lie in every minimum set, contradiction.
  have hmem : v ∈ S0.erase v := hfix.2 (S0.erase v) ⟨hdom_erase, hcard_erase_eq⟩
  exact Finset.notMem_erase v S0 hmem
See it in the graphDiscuss this resultChallenge it