digraph_semisaturation_isolated_edge_bound
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
- digraph_semisaturation_bounded_of_isolated_edgeLet G : Digraph V be a finite oriented digraph on vertex type V with DecidableEq V and DecidableRel G.Adj such that digraph_is_oriented G…
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).
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₀.
obtain ⟨u, v, huv, hiso⟩ := he use 3 * Fintype.card V intro n hn
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 ι.
uses
Fintype.card_prod,Fintype.card_fin,Function.Embedding.nonempty_of_card_lehave 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
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.
uses
Classical.decRellet 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 _
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.
uses
Finset.mem_filter.mp,Finset.mem_of_mem_erasehave 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
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.
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
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.
uses
if_pos,if_neg,False.elimlet 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
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.
uses
congr_arg,Prod.fst,Prod.snd,Or.inl,Or.inr,Prod.ext,if_neg,Finset.mem_erase,Finset.mem_filter,Finset.mem_univrefine ⟨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⟩
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.
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_producthave 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
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).
uses
Nat.sInf_lehave 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.
- The existence of an index i ∈ {0, 1, 2} whose copy avoids both x and y (lines 32–64) is established by an exhaustive 8-way case split ruling out all ways x and y could intersect two copies simultaneously.
- Adjacency in the constructed digraph H is declared decidable using noncomputable classical logic (`Classical.decRel`).
- Step 6 uses `aesop` automation to close the final injective case, and Step 8 uses `omega` to close the finset cardinality inequality.
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.
/-- 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