AFTD Auto-Formalizing Theoretical Domains

digraph_semisaturation_isolated_edge_bound

theoremverified

If G : Digraph V is a finite oriented digraph with DecidableEq V and DecidableRel G.Adj satisfying digraph_is_oriented G and digraph_has_isolated_edge G, then there exists n₀ : ℕ such that for all n ≥ n₀, digraph_ssat n G ≤ 3 * (digraph_edge_count G - 1).

Statement

theorem digraph_semisaturation_isolated_edge_bound {V : Type*} [Fintype V] [DecidableEq V] (G : Digraph V) [DecidableRel G.Adj] (hG : digraph_is_oriented G) (he : digraph_has_isolated_edge G) : ∃ n₀ : ℕ, ∀ n ≥ n₀, digraph_ssat n G ≤ 3 * (digraph_edge_count G - 1)
Source
arXiv:2610.18600 Lemma 2.1
Verified
24 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 5
  • digraph_ssatFor a natural number n and a digraph G : Digraph V on vertex type V, digraph_ssat n G is the infimum of the set of all natural numbers k :…
  • digraph_is_orientedA digraph G : Digraph V on vertex type V is oriented (digraph_is_oriented G) if for all vertices u v : V, G.Adj u v implies ¬ G.Adj v u.
  • digraph_has_isolated_edgeA digraph G on vertex type V has an isolated edge if there exist vertices u and v such that G has a directed edge from u to v, and every…
  • digraph_edge_countThe number m of edges (arcs) of a finite digraph G.
  • digraph_is_semisaturatingA host digraph H : Digraph W on vertex type W semisaturates a digraph G : Digraph V on vertex type V (digraph_is_semisaturating H G) if…
Used by 1

Read back from the Lean

Given a finite type $V$ with decidable equality and a directed graph $G$ on $V$ with decidable adjacency relation $G.\text{Adj}$, assume: 1. $G$ is oriented: for all $u, v \in V$, if $G.\text{Adj } u\ v$ then $\neg G.\text{Adj } v\ u$. 2. $G$ has an isolated edge: there exist vertices $u, v \in V$ such that $G.\text{Adj } u\ v$, and for all $w \in V$, if $G.\text{Adj } u\ w$, $G.\text{Adj } w\ u$, $G.\text{Adj } v\ w$, or $G.\text{Adj } w\ v$, then $w = u$ or $w = v$. Then there exists a threshold $n_0 \in \mathbb{N}$ such that for all $n \ge n_0$, the directed semisaturation number $\text{digraph\_ssat } n\ G$ is at most $3 \cdot (|E(G)| - 1)$, where $|E(G)|$ is the number of directed edges of $G$. Here $\text{digraph\_ssat } n\ G$ is defined as the infimum of edge counts of all oriented graphs $H$ on vertex set $\text{Fin } n$ (with decidable adjacency) that are semisaturating for $G$ (meaning adding any missing undirected edge $x \to y$ creates an injective copy of $G$ using that edge, with all other edges of $G$ already present in $H$).

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 bound the semi-saturation number digraph_ssat n G for n ≥ 3|V|, the proof explicitly constructs a semi-saturating oriented graph H on Fin n. The graph H consists of three vertex-disjoint copies of G with the isolated edge (u, v) removed from each copy. For any missing edge (x, y) in H, at least one of the three copies contains neither x nor y, which allows G to be embedded into H ∪ {(x, y)} by sending (u, v) to (x, y) and placing all other vertices in that unused copy. Since (u, v) has no other incident edges in G, this embedding preserves all edges of G, and the total number of edges in H is at most 3(|E(G)| - 1).

  1. Fix an isolated edge (u, v) in G, choose the threshold n₀ = 3|V|, and let n ≥ n₀.

    From the hypothesis that G has an isolated edge, we obtain vertices u, v ∈ V such that u → v is an edge and no other edge of G is incident to u or v. We set n₀ = 3|V| and fix an arbitrary n ≥ n₀.

    lines 3–5

      obtain ⟨u, v, huv, hiso⟩ := he
      use 3 * Fintype.card V
      intro n hn
  2. There exists an injective embedding ι : {0, 1, 2} × V ↪ Fin n.

    The cardinality of {0, 1, 2} × V is 3|V|, while Fin n has cardinality n. Since n ≥ 3|V|, the cardinality of the domain is at most that of the codomain, guaranteeing the existence of an embedding ι.

    lines 6–10

    uses Fintype.card_prod, Fintype.card_fin, Function.Embedding.nonempty_of_card_le

      have hcard_le : Fintype.card (Fin 3 × V) ≤ Fintype.card (Fin n) := by
        rw [Fintype.card_prod, Fintype.card_fin, Fintype.card_fin]
        exact hn
      obtain ⟨ι⟩ : Nonempty (Fin 3 × V ↪ Fin n) :=
        Function.Embedding.nonempty_of_card_le hcard_le
  3. Construct a digraph H on Fin n consisting of three disjoint copies of G with the edge (u, v) removed.

    Let E' = E(G) \ {(u, v)} be the edges of G excluding the isolated edge (u, v). Define H to have an edge from x to y whenever there is some copy i ∈ {0, 1, 2} and an edge p ∈ E' such that x = ι(i, p.1) and y = ι(i, p.2). Adjacency in H is decidable by classical logic.

    lines 11–13

    uses Classical.decRel

      let E' := (Finset.univ.filter fun p : V × V => G.Adj p.1 p.2).erase (u, v)
      let H : Digraph (Fin n) := ⟨fun x y => ∃ i : Fin 3, ∃ p ∈ E', x = ι (i, p.1) ∧ y = ι (i, p.2)⟩
      have hd : DecidableRel H.Adj := Classical.decRel _
  4. The graph H is oriented.

    If H contained both directed edges x → y and y → x, they would arise from edges p ∈ E' in copy i and q ∈ E' in copy j. By injectivity of ι, we must have i = j, q.1 = p.2, and q.2 = p.1, meaning both p.1 → p.2 and p.2 → p.1 are edges in G, contradicting the hypothesis that G is oriented.

    lines 14–26

    uses Finset.mem_filter.mp, Finset.mem_of_mem_erase

      have h_semi : digraph_is_semisaturating H G := by
        refine ⟨?_, ?_⟩
        · intro x y hxy hyx
          rcases hxy with ⟨i, p, hp, rfl, rfl⟩
          rcases hyx with ⟨j, q, hq, hy, hx⟩
          have hq2 : (j, q.2) = (i, p.1) := ι.injective hx.symm
          have hq1 : (j, q.1) = (i, p.2) := ι.injective hy.symm
          have hp_adj : G.Adj p.1 p.2 := (Finset.mem_filter.mp (Finset.mem_of_mem_erase hp)).2
          have hq_adj : G.Adj q.1 q.2 := (Finset.mem_filter.mp (Finset.mem_of_mem_erase hq)).2
          injection hq1 with _ hq1_val
          injection hq2 with _ hq2_val
          rw [hq1_val, hq2_val] at hq_adj
          exact hG p.1 p.2 hp_adj hq_adj
  5. For any two distinct, non-adjacent vertices x, y in H, there exists a copy i ∈ {0, 1, 2} that contains neither x nor y.

    Because G is oriented, it has no self-loops, so u ≠ v. By injectivity of ι, any vertex in Fin n can belong to the image of at most one copy i ∈ {0, 1, 2}. Since there are three copies and at most two vertices x and y, at least one copy i must be disjoint from {x, y}; this is verified by an exhaustive case analysis eliminating all eight configurations in which x or y would belong to multiple copies.

    lines 27–64

    uses congr_arg, Prod.fst, not_and_or

        · intro x y hxy _ _
          have hloop (z : V) : ¬ G.Adj z z := fun h => hG z z h h
          have huv_ne : u ≠ v := by
            rintro rfl
            exact hloop u huv
          obtain ⟨i, hx, hy⟩ : ∃ i : Fin 3, (∀ w, ι (i, w) ≠ x) ∧ (∀ w, ι (i, w) ≠ y) := by
            have h_inj (i j : Fin 3) (w₁ w₂ : V) (h : ι (i, w₁) = ι (j, w₂)) : i = j := by
              have := ι.injective h
              exact congr_arg Prod.fst this
            have h_not_both (i j : Fin 3) (hij : i ≠ j) (z : Fin n) :
                (∃ w, ι (i, w) = z) → (∃ w, ι (j, w) = z) → False := by
              rintro ⟨w₁, hw₁⟩ ⟨w₂, hw₂⟩
              have : i = j := h_inj i j w₁ w₂ (hw₁.trans hw₂.symm)
              exact hij this
            let i0 : Fin 3 := 0
            let i1 : Fin 3 := 1
            let i2 : Fin 3 := 2
            have h01 : i0 ≠ i1 := by decide
            have h02 : i0 ≠ i2 := by decide
            have h12 : i1 ≠ i2 := by decide
            by_cases h0 : (∀ w, ι (i0, w) ≠ x) ∧ (∀ w, ι (i0, w) ≠ y)
            · exact ⟨i0, h0⟩
            by_cases h1 : (∀ w, ι (i1, w) ≠ x) ∧ (∀ w, ι (i1, w) ≠ y)
            · exact ⟨i1, h1⟩
            by_cases h2 : (∀ w, ι (i2, w) ≠ x) ∧ (∀ w, ι (i2, w) ≠ y)
            · exact ⟨i2, h2⟩
            exfalso
            rw [not_and_or] at h0 h1 h2
            push Not at h0 h1 h2
            rcases h0 with h0x | h0y <;> rcases h1 with h1x | h1y <;> rcases h2 with h2x | h2y
            · exact h_not_both i0 i1 h01 x h0x h1x
            · exact h_not_both i0 i1 h01 x h0x h1x
            · exact h_not_both i0 i2 h02 x h0x h2x
            · exact h_not_both i1 i2 h12 y h1y h2y
            · exact h_not_both i1 i2 h12 x h1x h2x
            · exact h_not_both i0 i2 h02 y h0y h2y
            · exact h_not_both i0 i1 h01 y h0y h1y
            · exact h_not_both i0 i1 h01 y h0y h1y
  6. Define a map f : V → Fin n sending u ↦ x, v ↦ y, and all other w ↦ ι(i, w), and show that f is injective. automation

    We send u to x and v to y (which are distinct), and embed every other vertex w into the untouched copy i via ι(i, w). Since neither x nor y lies in the image of copy i, and ι is injective, all potential collisions between different branches evaluate to false, proving that f is injective.

    lines 65–82

    uses if_pos, if_neg, False.elim

          let f : V → Fin n := fun w => if w = u then x else if w = v then y else ι (i, w)
          have hfu : f u = x := if_pos rfl
          have hfv : f v = y := by
            dsimp [f]
            rw [if_neg huv_ne.symm, if_pos rfl]
          have hfinj : Function.Injective f := by
            intro a b hab
            dsimp only [f] at hab
            split_ifs at hab with h1 h2 h3 h4 h5 <;> try (subst_vars; rfl)
            all_goals
              first
              | exact False.elim (hxy hab)
              | exact False.elim (hxy hab.symm)
              | exact False.elim (hx _ hab)
              | exact False.elim (hx _ hab.symm)
              | exact False.elim (hy _ hab)
              | exact False.elim (hy _ hab.symm)
              | have := ι.injective hab; aesop
  7. The map f preserves the edges of G, showing that H is semi-saturating for G.

    By definition, (f(u), f(v)) = (x, y), which covers the missing edge (u, v). For any other edge (a, b) ∈ E(G) with (a, b) ≠ (u, v), the fact that (u, v) is isolated implies that neither a nor b can be u or v (otherwise the other endpoint would have to be u or v, yielding a self-loop, a bidirectional edge, or the edge (u, v) itself). Hence f(a) = ι(i, a) and f(b) = ι(i, b), so f(a) → f(b) is an edge in H. Together with orientation, this shows H is semi-saturating for G.

    lines 83–129

    uses congr_arg, Prod.fst, Prod.snd, Or.inl, Or.inr, Prod.ext, if_neg, Finset.mem_erase, Finset.mem_filter, Finset.mem_univ

          refine ⟨f, hfinj, ?_, ⟨u, v, huv, hfu, hfv⟩⟩
          intro a b hab
          by_cases hab_eq : (a, b) = (u, v)
          · have ha : a = u := congr_arg Prod.fst hab_eq
            have hb : b = v := congr_arg Prod.snd hab_eq
            right
            rw [ha, hb, hfu, hfv]
            exact ⟨rfl, rfl⟩
          · left
            have ha_ne_u : a ≠ u := by
              intro ha
              have hab' : G.Adj u b := ha ▸ hab
              have : b = u ∨ b = v := hiso b (Or.inl hab')
              cases this with
              | inl h1 => exact hloop u (h1 ▸ hab')
              | inr h2 => exact hab_eq (Prod.ext ha h2)
            have ha_ne_v : a ≠ v := by
              intro ha
              have hab' : G.Adj v b := ha ▸ hab
              have : b = u ∨ b = v := hiso b (Or.inr (Or.inr (Or.inl hab')))
              cases this with
              | inl h1 => exact hG u v huv (h1 ▸ hab')
              | inr h2 => exact hloop v (h2 ▸ hab')
            have hb_ne_u : b ≠ u := by
              intro hb
              have hab' : G.Adj a u := hb ▸ hab
              have : a = u ∨ a = v := hiso a (Or.inr (Or.inl hab'))
              cases this with
              | inl h1 => exact hloop u (h1 ▸ hab')
              | inr h2 => exact hG u v huv (h2 ▸ hab')
            have hb_ne_v : b ≠ v := by
              intro hb
              have hab' : G.Adj a v := hb ▸ hab
              have : a = u ∨ a = v := hiso a (Or.inr (Or.inr (Or.inr hab')))
              cases this with
              | inl h1 => exact hab_eq (Prod.ext h1 hb)
              | inr h2 => exact hloop v (h2 ▸ hab')
            have hfa : f a = ι (i, a) := by
              dsimp [f]
              rw [if_neg ha_ne_u, if_neg ha_ne_v]
            have hfb : f b = ι (i, b) := by
              dsimp [f]
              rw [if_neg hb_ne_u, if_neg hb_ne_v]
            rw [hfa, hfb]
            refine ⟨i, (a, b), ?_, rfl, rfl⟩
            rw [Finset.mem_erase, Finset.mem_filter]
            exact ⟨hab_eq, Finset.mem_univ _, hab⟩
  8. The edge count of H is at most 3(|E(G)| - 1). automation

    The set E' has size |E(G)| - 1 because (u, v) was removed. The edge set of H is a subset of the image of {0, 1, 2} × E' under ι, so |E(H)| ≤ |{0, 1, 2} × E'| = 3|E'| = 3(|E(G)| - 1). Linear arithmetic closes the inequality.

    lines 130–152

    uses Finset.card_erase_of_mem, Finset.mem_image, Finset.mem_product.mpr, Finset.mem_univ, Finset.card_le_card, Finset.card_image_le, Finset.card_product

      have h_count : digraph_edge_count H ≤ 3 * (digraph_edge_count G - 1) := by
        have hE' : E'.card = digraph_edge_count G - 1 := by
          have : (u, v) ∈ Finset.univ.filter fun p : V × V => G.Adj p.1 p.2 := by
            simp [huv]
          rw [Finset.card_erase_of_mem this]
          rfl
        have hsub : (Finset.univ.filter fun p : Fin n × Fin n => H.Adj p.1 p.2) ⊆
            ((Finset.univ : Finset (Fin 3)) ×ˢ E').image (fun ip => (ι (ip.1, ip.2.1), ι (ip.1, ip.2.2))) := by
          intro ⟨x, y⟩ hmem
          simp only [Finset.mem_filter, Finset.mem_univ, true_and] at hmem
          rcases hmem with ⟨i, p, hp, rfl, rfl⟩
          rw [Finset.mem_image]
          exact ⟨(i, p), Finset.mem_product.mpr ⟨Finset.mem_univ i, hp⟩, rfl⟩
        have hle1 : (Finset.univ.filter fun p : Fin n × Fin n => H.Adj p.1 p.2).card ≤
            (((Finset.univ : Finset (Fin 3)) ×ˢ E').image (fun ip => (ι (ip.1, ip.2.1), ι (ip.1, ip.2.2)))).card :=
          Finset.card_le_card hsub
        have hle2 : (((Finset.univ : Finset (Fin 3)) ×ˢ E').image (fun ip => (ι (ip.1, ip.2.1), ι (ip.1, ip.2.2)))).card ≤
            ((Finset.univ : Finset (Fin 3)) ×ˢ E').card := Finset.card_image_le
        have hcard : ((Finset.univ : Finset (Fin 3)) ×ˢ E').card = 3 * (digraph_edge_count G - 1) := by
          rw [Finset.card_product]
          simp [hE']
        change (Finset.univ.filter fun p : Fin n × Fin n => H.Adj p.1 p.2).card ≤ 3 * (digraph_edge_count G - 1)
        omega
  9. The semi-saturation number digraph_ssat n G is at most 3(|E(G)| - 1).

    By definition, digraph_ssat n G is the infimum of the edge counts of all graphs on Fin n that are semi-saturating for G. Since H is such a graph, digraph_ssat n G ≤ |E(H)| ≤ 3(|E(G)| - 1).

    lines 153–157

    uses Nat.sInf_le

      have h_ssat_le : digraph_ssat n G ≤ digraph_edge_count H := by
        unfold digraph_ssat
        apply Nat.sInf_le
        exact ⟨H, hd, h_semi, rfl⟩
      exact h_ssat_le.trans h_count
Classical.decRel
By the law of excluded middle, any binary relation is decidable.
congr_arg
Applying a function to equal inputs produces equal outputs.
False.elim
From a contradiction (False), any conclusion follows.
Finset.card_image_le
The cardinality of the image of a finite set under any map is at most the cardinality of the domain set.
Finset.card_product
The cardinality of the Cartesian product of two finite sets is the product of their cardinalities.
Finset.card_le_card
If s ⊆ t for finite sets, then |s| ≤ |t|.
Finset.card_erase_of_mem
Removing an element present in a finite set decreases its cardinality by 1.
Finset.mem_erase
An element belongs to s.erase b if and only if it is not equal to b and belongs to s.
Finset.mem_filter
An element belongs to a filtered finite set if and only if it belongs to the base set and satisfies the predicate.
Finset.mem_filter.mp
Extracts the property that an element in a filtered finite set satisfies the filtering predicate.
Finset.mem_image
An element belongs to the image of a finite set under f if and only if it is the image of some element in the set.
Finset.mem_of_mem_erase
If an element belongs to s.erase a, then it belongs to s.
Finset.mem_product.mpr
A pair belongs to the product s ×ˢ t if its first component is in s and its second is in t.
Finset.mem_univ
Every element of a finite type belongs to the universal finset Finset.univ.
Fintype.card_fin
The cardinality of the standard finite set Fin n is n.
Fintype.card_prod
The cardinality of the Cartesian product of two finite types is the product of their cardinalities.
Function.Embedding.nonempty_of_card_le
If |α| ≤ |β| for finite types, then there exists an injective embedding α ↪ β.
if_neg
If the condition c is false, then (if c then t else e) evaluates to e.
if_pos
If the condition c is true, then (if c then t else e) evaluates to t.
Nat.sInf_le
The infimum of a set of natural numbers is less than or equal to any member of the set.
not_and_or
De Morgan's law: ¬(a ∧ b) is equivalent to ¬a ∨ ¬b.
Or.inl
Given a proof of a, establishes the disjunction a ∨ b.
Or.inr
Given a proof of b, establishes the disjunction a ∨ b.
Prod.ext
Two pairs are equal if their first components are equal and their second components are equal.
Prod.fst
The projection from an ordered pair to its first component.
Prod.snd
The projection from an ordered pair to its second component.

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

/-- Upper bound 3(|E(G)| - 1) on ssat(n, G) for oriented graphs containing an isolated edge. -/theorem digraph_semisaturation_isolated_edge_bound {V : Type*} [Fintype V] [DecidableEq V] (G : Digraph V) [DecidableRel G.Adj] (hG : digraph_is_oriented G) (he : digraph_has_isolated_edge G) : ∃ n₀ : ℕ, ∀ n ≥ n₀, digraph_ssat n G ≤ 3 * (digraph_edge_count G - 1) := by  obtain ⟨u, v, huv, hiso⟩ := he  use 3 * Fintype.card V  intro n hn  have hcard_le : Fintype.card (Fin 3 × V) ≤ Fintype.card (Fin n) := by    rw [Fintype.card_prod, Fintype.card_fin, Fintype.card_fin]    exact hn  obtain ⟨ι⟩ : Nonempty (Fin 3 × V ↪ Fin n) :=    Function.Embedding.nonempty_of_card_le hcard_le  let E' := (Finset.univ.filter fun p : V × V => G.Adj p.1 p.2).erase (u, v)  let H : Digraph (Fin n) := ⟨fun x y => ∃ i : Fin 3, ∃ p ∈ E', x = ι (i, p.1) ∧ y = ι (i, p.2)⟩  have hd : DecidableRel H.Adj := Classical.decRel _  have h_semi : digraph_is_semisaturating H G := by    refine ⟨?_, ?_⟩    · intro x y hxy hyx      rcases hxy with ⟨i, p, hp, rfl, rfl⟩      rcases hyx with ⟨j, q, hq, hy, hx⟩      have hq2 : (j, q.2) = (i, p.1) := ι.injective hx.symm      have hq1 : (j, q.1) = (i, p.2) := ι.injective hy.symm      have hp_adj : G.Adj p.1 p.2 := (Finset.mem_filter.mp (Finset.mem_of_mem_erase hp)).2      have hq_adj : G.Adj q.1 q.2 := (Finset.mem_filter.mp (Finset.mem_of_mem_erase hq)).2      injection hq1 with _ hq1_val      injection hq2 with _ hq2_val      rw [hq1_val, hq2_val] at hq_adj      exact hG p.1 p.2 hp_adj hq_adj    · intro x y hxy _ _      have hloop (z : V) : ¬ G.Adj z z := fun h => hG z z h h      have huv_ne : u ≠ v := by        rintro rfl        exact hloop u huv      obtain ⟨i, hx, hy⟩ : ∃ i : Fin 3, (∀ w, ι (i, w) ≠ x) ∧ (∀ w, ι (i, w) ≠ y) := by        have h_inj (i j : Fin 3) (w₁ w₂ : V) (h : ι (i, w₁) = ι (j, w₂)) : i = j := by          have := ι.injective h          exact congr_arg Prod.fst this        have h_not_both (i j : Fin 3) (hij : i ≠ j) (z : Fin n) :            (∃ w, ι (i, w) = z) → (∃ w, ι (j, w) = z) → False := by          rintro ⟨w₁, hw₁⟩ ⟨w₂, hw₂⟩          have : i = j := h_inj i j w₁ w₂ (hw₁.trans hw₂.symm)          exact hij this        let i0 : Fin 3 := 0        let i1 : Fin 3 := 1        let i2 : Fin 3 := 2        have h01 : i0 ≠ i1 := by decide        have h02 : i0 ≠ i2 := by decide        have h12 : i1 ≠ i2 := by decide        by_cases h0 : (∀ w, ι (i0, w) ≠ x) ∧ (∀ w, ι (i0, w) ≠ y)        · exact ⟨i0, h0⟩        by_cases h1 : (∀ w, ι (i1, w) ≠ x) ∧ (∀ w, ι (i1, w) ≠ y)        · exact ⟨i1, h1⟩        by_cases h2 : (∀ w, ι (i2, w) ≠ x) ∧ (∀ w, ι (i2, w) ≠ y)        · exact ⟨i2, h2⟩        exfalso        rw [not_and_or] at h0 h1 h2        push Not at h0 h1 h2        rcases h0 with h0x | h0y <;> rcases h1 with h1x | h1y <;> rcases h2 with h2x | h2y        · exact h_not_both i0 i1 h01 x h0x h1x        · exact h_not_both i0 i1 h01 x h0x h1x        · exact h_not_both i0 i2 h02 x h0x h2x        · exact h_not_both i1 i2 h12 y h1y h2y        · exact h_not_both i1 i2 h12 x h1x h2x        · exact h_not_both i0 i2 h02 y h0y h2y        · exact h_not_both i0 i1 h01 y h0y h1y        · exact h_not_both i0 i1 h01 y h0y h1y      let f : V → Fin n := fun w => if w = u then x else if w = v then y else ι (i, w)      have hfu : f u = x := if_pos rfl      have hfv : f v = y := by        dsimp [f]        rw [if_neg huv_ne.symm, if_pos rfl]      have hfinj : Function.Injective f := by        intro a b hab        dsimp only [f] at hab        split_ifs at hab with h1 h2 h3 h4 h5 <;> try (subst_vars; rfl)        all_goals          first          | exact False.elim (hxy hab)          | exact False.elim (hxy hab.symm)          | exact False.elim (hx _ hab)          | exact False.elim (hx _ hab.symm)          | exact False.elim (hy _ hab)          | exact False.elim (hy _ hab.symm)          | have := ι.injective hab; aesop      refine ⟨f, hfinj, ?_, ⟨u, v, huv, hfu, hfv⟩⟩      intro a b hab      by_cases hab_eq : (a, b) = (u, v)      · have ha : a = u := congr_arg Prod.fst hab_eq        have hb : b = v := congr_arg Prod.snd hab_eq        right        rw [ha, hb, hfu, hfv]        exact ⟨rfl, rfl⟩      · left        have ha_ne_u : a ≠ u := by          intro ha          have hab' : G.Adj u b := ha ▸ hab          have : b = u ∨ b = v := hiso b (Or.inl hab')          cases this with          | inl h1 => exact hloop u (h1 ▸ hab')          | inr h2 => exact hab_eq (Prod.ext ha h2)        have ha_ne_v : a ≠ v := by          intro ha          have hab' : G.Adj v b := ha ▸ hab          have : b = u ∨ b = v := hiso b (Or.inr (Or.inr (Or.inl hab')))          cases this with          | inl h1 => exact hG u v huv (h1 ▸ hab')          | inr h2 => exact hloop v (h2 ▸ hab')        have hb_ne_u : b ≠ u := by          intro hb          have hab' : G.Adj a u := hb ▸ hab          have : a = u ∨ a = v := hiso a (Or.inr (Or.inl hab'))          cases this with          | inl h1 => exact hloop u (h1 ▸ hab')          | inr h2 => exact hG u v huv (h2 ▸ hab')        have hb_ne_v : b ≠ v := by          intro hb          have hab' : G.Adj a v := hb ▸ hab          have : a = u ∨ a = v := hiso a (Or.inr (Or.inr (Or.inr hab')))          cases this with          | inl h1 => exact hab_eq (Prod.ext h1 hb)          | inr h2 => exact hloop v (h2 ▸ hab')        have hfa : f a = ι (i, a) := by          dsimp [f]          rw [if_neg ha_ne_u, if_neg ha_ne_v]        have hfb : f b = ι (i, b) := by          dsimp [f]          rw [if_neg hb_ne_u, if_neg hb_ne_v]        rw [hfa, hfb]        refine ⟨i, (a, b), ?_, rfl, rfl⟩        rw [Finset.mem_erase, Finset.mem_filter]        exact ⟨hab_eq, Finset.mem_univ _, hab⟩  have h_count : digraph_edge_count H ≤ 3 * (digraph_edge_count G - 1) := by    have hE' : E'.card = digraph_edge_count G - 1 := by      have : (u, v) ∈ Finset.univ.filter fun p : V × V => G.Adj p.1 p.2 := by        simp [huv]      rw [Finset.card_erase_of_mem this]      rfl    have hsub : (Finset.univ.filter fun p : Fin n × Fin n => H.Adj p.1 p.2) ⊆        ((Finset.univ : Finset (Fin 3)) ×ˢ E').image (fun ip => (ι (ip.1, ip.2.1), ι (ip.1, ip.2.2))) := by      intro ⟨x, y⟩ hmem      simp only [Finset.mem_filter, Finset.mem_univ, true_and] at hmem      rcases hmem with ⟨i, p, hp, rfl, rfl⟩      rw [Finset.mem_image]      exact ⟨(i, p), Finset.mem_product.mpr ⟨Finset.mem_univ i, hp⟩, rfl⟩    have hle1 : (Finset.univ.filter fun p : Fin n × Fin n => H.Adj p.1 p.2).card ≤        (((Finset.univ : Finset (Fin 3)) ×ˢ E').image (fun ip => (ι (ip.1, ip.2.1), ι (ip.1, ip.2.2)))).card :=      Finset.card_le_card hsub    have hle2 : (((Finset.univ : Finset (Fin 3)) ×ˢ E').image (fun ip => (ι (ip.1, ip.2.1), ι (ip.1, ip.2.2)))).card ≤        ((Finset.univ : Finset (Fin 3)) ×ˢ E').card := Finset.card_image_le    have hcard : ((Finset.univ : Finset (Fin 3)) ×ˢ E').card = 3 * (digraph_edge_count G - 1) := by      rw [Finset.card_product]      simp [hE']    change (Finset.univ.filter fun p : Fin n × Fin n => H.Adj p.1 p.2).card ≤ 3 * (digraph_edge_count G - 1)    omega  have h_ssat_le : digraph_ssat n G ≤ digraph_edge_count H := by    unfold digraph_ssat    apply Nat.sInf_le    exact ⟨H, hd, h_semi, rfl⟩  exact h_ssat_le.trans h_count
See it in the graphDiscuss this resultChallenge it