disjoint_minimal_nonfaces_dimension
Let Δ be an abstract simplicial complex on an n-element vertex set V, pure of facet size d, with connected dual graph. If its minimal nonfaces are pairwise disjoint and there are s of them, then d = n - s.
Statement
theorem disjoint_minimal_nonfaces_dimension {V : Type*} [DecidableEq V] [Fintype V] (Δ : AbstractSimplicialComplex V) (n d s : ℕ) (hn : Fintype.card V = n) (hpure : simplicial_is_pure Δ d) (hconn : (simplicial_dual_graph Δ d).Connected) (M_set : Finset (Finset V)) (hs : M_set.card = s) (hM_all : ∀ M, simplicial_is_minimal_nonface Δ M ↔ M ∈ M_set) (hM_disj : ∀ M₁ ∈ M_set, ∀ M₂ ∈ M_set, M₁ ≠ M₂ → Disjoint M₁ M₂) : d = n - s
- Source
- arXiv:2611.08071 Lemma 5.1 and Corollary 5.2
- Verified
- 07 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 4
- simplicial_is_pureAn abstract simplicial complex Δ is pure of facet size d if every facet of Δ has cardinality d.
- simplicial_dual_graphThe dual graph of an abstract simplicial complex pure of facet size d is the simple graph whose vertices are the facets of Δ, where two…
- simplicial_is_minimal_nonfaceGiven an abstract simplicial complex Δ of type AbstractSimplicialComplex V, a finite subset M of V of cardinality at least 2 is a minimal…
- simplicial_is_facetA face F of an abstract simplicial complex Δ is a facet if it is maximal with respect to inclusion among all faces of Δ.
Read back from the Lean
Let V be a finite type with decidable equality, and let Δ be an abstract simplicial complex on V. Let n, d, and s be natural numbers such that:
1. hn: The cardinality of V is n.
2. hpure: Δ is pure of dimension d (every facet of Δ has cardinality d).
3. hconn: The dual graph of Δ (whose vertices are facets of Δ, with an edge between two facets if they are distinct and their intersection has cardinality d - 1) is connected.
4. M_set: A finite set of finite subsets of V.
5. hs: The cardinality of M_set is s.
6. hM_all: For every finite subset M of V, M is in M_set if and only if M is a minimal nonface of Δ (meaning 2 ≤ M.card, M ∉ Δ.faces, and every nonempty proper subset T ⊂ M is in Δ.faces).
7. hM_disj: The sets in M_set are pairwise disjoint (for any M₁, M₂ ∈ M_set, if M₁ ≠ M₂, then Disjoint M₁ M₂).
Then d = n - s.
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
Connectedness of the dual graph guarantees the existence of a facet G of size d. In the degenerate case where the vertex set is empty, d = n = s = 0 holds immediately. In the general case, every vertex outside G extends G to a nonface, which contains a minimal nonface. Because the minimal nonfaces are pairwise disjoint, each minimal nonface intersects the complement V \ G in exactly one vertex, partitioning V \ G into s singletons. Thus |V \ G| = s, and the partition V = G ∪ (V \ G) gives n = d + s, which yields d = n - s.
There exists a facet G of size d, and any nonempty subset of a face of Δ is a face.
Connectedness of the simplicial dual graph implies that the graph is nonempty, so there exists at least one facet G. By purity of Δ, G has cardinality d. By definition of a facet, G is maximal among faces of Δ. Furthermore, by the simplicial complex property, any nonempty subset of a face is also a face.
classical -- a facet exists because the dual graph is connected obtain ⟨⟨G, hGfacet⟩⟩ := hconn.nonempty have hGcard : G.card = d := hpure G hGfacet have hGmem : G ∈ Δ.faces := hGfacet.1 have hGmax : ∀ H ∈ Δ.faces, G ⊆ H → G = H := hGfacet.2 -- faces are closed under nonempty subsets have hlower : ∀ {a b : Finset V}, a ∈ Δ.faces → b ⊆ a → b.Nonempty → b ∈ Δ.faces := fun {a b} ha hba hb => (Δ.isRelLowerSet_faces ha).2 hba hb
If the vertex set V is empty, then d = 0, n = 0, and s = 0, so d = n - s holds. automation
We case split on whether the universal vertex set is empty. If it is empty, the type V is empty, so its cardinality n is 0. Since G is a subset of V, G is empty, which gives d = |G| = 0. Minimal nonfaces must have size at least 2, but no subset of an empty set has size 2, so the set of minimal nonfaces is empty and s = 0. Linear arithmetic resolves 0 = 0 - 0.
uses
Finset.eq_empty_or_nonempty,Finset.univ_eq_empty_iff.mp,Finset.card_eq_zero,Finset.not_nonempty_iff_eq_empty,Fintype.card_eq_zero_iff.mprrcases Finset.eq_empty_or_nonempty (Finset.univ : Finset V) with huniv | huniv · -- degenerate case: no vertices have hEmpty : IsEmpty V := Finset.univ_eq_empty_iff.mp huniv have hd0 : d = 0 := by rw [← hGcard, Finset.card_eq_zero, ← Finset.not_nonempty_iff_eq_empty] rintro ⟨x, -⟩ exact hEmpty.false x have hn0 : n = 0 := by rw [← hn] exact Fintype.card_eq_zero_iff.mpr hEmpty have hs0 : s = 0 := by have hMs : M_set = ∅ := by rw [← Finset.not_nonempty_iff_eq_empty] rintro ⟨M, hM⟩ have h2 : 2 ≤ M.card := ((hM_all M).mpr hM).1 have hMe : M = ∅ := by rw [← Finset.not_nonempty_iff_eq_empty] rintro ⟨x, -⟩ exact hEmpty.false x rw [hMe] at h2 simp at h2 rw [← hs, hMs] simp omega
When V is nonempty, the facet dimension satisfies d ≥ 1.
Suppose for contradiction that G has cardinality 0, so G = ∅. Since V is nonempty, pick any vertex v. The singleton {v} is a face of Δ. Because ∅ ⊆ {v} and G is maximal among faces, G = {v}. But {v} has size 1, contradicting that |G| = 0. Hence d = |G| ≥ 1.
uses
Finset.card_eq_zero.mp,Finset.empty_subset,Finset.card_singleton· -- main case: `d ≥ 1` because facets are nonempty have hd1 : 1 ≤ d := by have hpos : 0 < G.card := by by_contra h have hz : G.card = 0 := by omega have hGe : G = ∅ := Finset.card_eq_zero.mp hz obtain ⟨v, -⟩ := huniv have hv : ({v} : Finset V) ∈ Δ.faces := Δ.singleton_mem v have hsub : G ⊆ {v} := by rw [hGe]; exact Finset.empty_subset _ have heq : G = {v} := hGmax {v} hv hsub have hc : ({v} : Finset V).card = 0 := by rw [← heq, hGe]; simp rw [Finset.card_singleton] at hc omega omega
Every nonface with at least two vertices contains a minimal nonface.
Given a nonface N of size at least 2, consider the finite collection of all subsets of N that are nonfaces of size at least 2. This collection is nonempty since it contains N. By Finset.exists_min_image, choose a subset M in this collection of minimal cardinality. If M had a proper nonempty subset T that was not a face, then since singletons are faces, T would have size at least 2, contradicting the minimality of |M|. Thus every proper nonempty subset of M is a face, so M is a minimal nonface.
uses
Finset.exists_min_image,Finset.mem_filter,Finset.mem_univ,true_and,Finset.card_lt_card-- (A) every nonface with at least two vertices contains a minimal nonface have hmin_exists : ∀ N : Finset V, N ∉ Δ.faces → 2 ≤ N.card → ∃ M : Finset V, simplicial_is_minimal_nonface Δ M ∧ M ⊆ N := by intro N hN hN2 have hne : (Finset.univ.filter (fun M : Finset V => M ⊆ N ∧ M ∉ Δ.faces ∧ 2 ≤ M.card)).Nonempty := ⟨N, by simp [hN, hN2]⟩ obtain ⟨M, hMmem, hMmin⟩ := Finset.exists_min_image (Finset.univ.filter (fun M : Finset V => M ⊆ N ∧ M ∉ Δ.faces ∧ 2 ≤ M.card)) (fun M => M.card) hne simp only [Finset.mem_filter, Finset.mem_univ, true_and] at hMmem obtain ⟨hMN, hMnotface, hM2⟩ := hMmem refine ⟨M, ⟨hM2, hMnotface, ?_⟩, hMN⟩ intro T hTM hTne by_contra hTnotface have hT2 : 2 ≤ T.card := by have hpos : 0 < T.card := Finset.card_pos.mpr hTne have hne1 : T.card ≠ 1 := by intro h1 obtain ⟨x, rfl⟩ := Finset.card_eq_one.mp h1 exact hTnotface (Δ.singleton_mem x) omega have hTfilt : T ∈ Finset.univ.filter (fun M : Finset V => M ⊆ N ∧ M ∉ Δ.faces ∧ 2 ≤ M.card) := by simp only [Finset.mem_filter, Finset.mem_univ, true_and] exact ⟨hTM.subset.trans hMN, hTnotface, hT2⟩ have hle := hMmin T hTfilt have hlt : T.card < M.card := Finset.card_lt_card hTM omega
Adding any vertex outside a facet produces a nonface.
Let H be a facet and v ∉ H. If H ∪ {v} were a face, then by maximality of H among faces of Δ, H = H ∪ {v}, which would imply v ∈ H, a contradiction.
uses
Finset.subset_union_left,Finset.mem_union_right,Finset.mem_singleton_self-- (B) adding a vertex outside a facet always produces a nonface have hfac_insert : ∀ (H : Finset V) (v : V), simplicial_is_facet Δ H → v ∉ H → H ∪ {v} ∉ Δ.faces := by intro H v hH hv hmem have heq : H = H ∪ {v} := hH.2 _ hmem Finset.subset_union_left have hv1 : v ∈ H ∪ {v} := Finset.mem_union_right H (Finset.mem_singleton_self v) rw [← heq] at hv1 exact hv hv1
Every vertex v outside a facet H is contained in some minimal nonface M ∈ M_set with M ⊆ H ∪ {v}.
The set H ∪ {v} has size |H| + 1 = d + 1 ≥ 2 and is not a face. It therefore contains a minimal nonface M ∈ M_set. Since H is a face, all nonempty subsets of H are faces, so M cannot be a subset of H. Thus M contains an element not in H, which must be v.
uses
Finset.card_union_of_disjoint,Nat.add_le_add_right,Finset.mem_union,Finset.mem_singleton-- (C) every vertex outside a facet lies in a minimal nonface contained in -- the facet together with that vertex have hcover : ∀ (H : Finset V) (v : V), simplicial_is_facet Δ H → v ∉ H → ∃ M ∈ M_set, v ∈ M ∧ M ⊆ H ∪ {v} := by intro H v hH hv have hnotface : H ∪ {v} ∉ Δ.faces := hfac_insert H v hH hv have hHcard : H.card = d := hpure H hH have hcard2 : 2 ≤ (H ∪ {v}).card := by have h1 : (H ∪ {v}).card = H.card + 1 := Finset.card_union_of_disjoint (Finset.disjoint_singleton_right.mpr hv) rw [h1, hHcard] exact Nat.add_le_add_right hd1 1 obtain ⟨M, hMmin, hMH⟩ := hmin_exists (H ∪ {v}) hnotface hcard2 have hMmem : M ∈ M_set := (hM_all M).mp hMmin have hM2 : 2 ≤ M.card := hMmin.1 have hMnotface : M ∉ Δ.faces := hMmin.2.1 have hMpos : 0 < M.card := by omega have hMnotsub : ¬ M ⊆ H := fun hsub => hMnotface (hlower hH.1 hsub (Finset.card_pos.mp hMpos)) obtain ⟨x, hxM, hxH⟩ := Finset.not_subset.mp hMnotsub have hx : x ∈ H ∪ {v} := hMH hxM rw [Finset.mem_union] at hx have hvM : v ∈ M := by rcases hx with h | h · exact absurd h hxH · rw [Finset.mem_singleton] at h rw [h] at hxM exact hxM exact ⟨M, hMmem, hvM, hMH⟩
Each minimal nonface M ∈ M_set meets the complement V \ G in exactly one vertex, so |M \ G| = 1.
Since M is not a face while G is, M ⊈ G, so there is at least one vertex v ∈ M \ G. For any x ∈ M \ G, the covering property provides a minimal nonface M' ∈ M_set with x ∈ M' and M' ⊆ G ∪ {x}. Because x ∈ M ∩ M' and minimal nonfaces are pairwise disjoint, M' = M, so M ⊆ G ∪ {x}. Then v ∈ M implies v ∈ G ∪ {x}, which forces v = x since v ∉ G. Thus M \ G = {v}, which is a singleton of cardinality 1.
uses
Finset.Subset.antisymm,Finset.mem_sdiff,Finset.mem_union,Finset.mem_singleton,Finset.card_singleton-- (D) each minimal nonface contributes exactly one vertex outside `G` have huniq : ∀ M ∈ M_set, ∃ v : V, M \ G = {v} := by intro M hM have hM2 : 2 ≤ M.card := ((hM_all M).mpr hM).1 have hMnotface : M ∉ Δ.faces := ((hM_all M).mpr hM).2.1 have hMpos : 0 < M.card := by omega have hMnotsub : ¬ M ⊆ G := fun hsub => hMnotface (hlower hGmem hsub (Finset.card_pos.mp hMpos)) obtain ⟨v, hvM, hvG⟩ := Finset.not_subset.mp hMnotsub refine ⟨v, ?_⟩ apply Finset.Subset.antisymm · intro x hx rw [Finset.mem_sdiff] at hx obtain ⟨hxM, hxG⟩ := hx obtain ⟨M', hM', hxM', hM'sub⟩ := hcover G x hGfacet hxG have hM'eq : M' = M := by by_contra hne have hd := hM_disj M' hM' M hM hne exact (Finset.disjoint_left.mp hd) hxM' hxM rw [hM'eq] at hM'sub have hv' : v ∈ G ∪ {x} := hM'sub hvM rw [Finset.mem_union] at hv' rcases hv' with h | h · exact absurd h hvG · rw [Finset.mem_singleton] at h rw [Finset.mem_singleton] exact h.symm · intro x hx rw [Finset.mem_singleton] at hx rw [hx] exact Finset.mem_sdiff.mpr ⟨hvM, hvG⟩ have hcard_one : ∀ M ∈ M_set, (M \ G).card = 1 := by intro M hM obtain ⟨v, hv⟩ := huniq M hM rw [hv, Finset.card_singleton]
The complement V \ G is the disjoint union of the singletons M \ G over M ∈ M_set, and has cardinality s.
Every vertex outside G is covered by some minimal nonface M with M ⊆ G ∪ {x}, so V \ G = ⋃_{M ∈ M_set} (M \ G). Since the minimal nonfaces M ∈ M_set are pairwise disjoint, the singletons M \ G are also pairwise disjoint. Summing their cardinalities yields |V \ G| = ∑_{M ∈ M_set} 1 = |M_set| = s.
uses
Finset.Subset.antisymm,Finset.mem_sdiff,Finset.card_biUnion,Finset.sdiff_subset,Finset.sum_congr-- the complement of a facet is the disjoint union of these singletons have hVF : (Finset.univ \ G) = M_set.biUnion (fun M => M \ G) := by apply Finset.Subset.antisymm · intro x hx rw [Finset.mem_sdiff] at hx obtain ⟨-, hxG⟩ := hx obtain ⟨M, hM, hxM, -⟩ := hcover G x hGfacet hxG exact Finset.mem_biUnion.mpr ⟨M, hM, Finset.mem_sdiff.mpr ⟨hxM, hxG⟩⟩ · intro x hx obtain ⟨M, hM, hxM⟩ := Finset.mem_biUnion.mp hx exact Finset.mem_sdiff.mpr ⟨Finset.mem_univ x, (Finset.mem_sdiff.mp hxM).2⟩ have hcardVF : (Finset.univ \ G).card = s := by rw [hVF, Finset.card_biUnion (fun M hM M' hM' hne => (hM_disj M hM M' hM' hne).mono Finset.sdiff_subset Finset.sdiff_subset)] rw [Finset.sum_congr rfl hcard_one] simp [hs]
The dimension formula d = n - s holds. automation
Partitioning the vertex set V into the facet G and its complement V \ G gives |V \ G| + |G| = |V|. Substituting |V \ G| = s, |G| = d, and |V| = n gives s + d = n, from which linear arithmetic concludes d = n - s.
uses
Finset.card_sdiff_add_card_eq_card,Finset.subset_univ,Finset.card_univhave hsum := Finset.card_sdiff_add_card_eq_card (Finset.subset_univ G) rw [hcardVF, hGcard, Finset.card_univ, hn] at hsum omega
Finset.card_univ- The cardinality of the universal finite set of a finite type equals the cardinality of the type.
Finset.subset_univ- Every finite set of elements of a finite type is a subset of the universal finite set.
Finset.card_sdiff_add_card_eq_card- If s is a subset of t, the cardinality of t \ s plus the cardinality of s equals the cardinality of t.
Finset.sum_congr- Two sums over finite sets are equal if the sets of indices are equal and the summands agree on every element.
Finset.sdiff_subset- The set difference s \ t is a subset of s.
Finset.card_biUnion- The cardinality of a union of pairwise disjoint finite sets is the sum of the cardinalities of the individual sets.
Finset.mem_sdiff- An element belongs to the set difference s \ t if and only if it belongs to s and does not belong to t.
Finset.Subset.antisymm- If two finite sets are subsets of each other, they are equal.
Finset.mem_singleton- An element b belongs to the singleton set {a} if and only if b = a.
Finset.mem_union- An element belongs to the union s ∪ t if and only if it belongs to s or it belongs to t.
Nat.add_le_add_right- Adding a natural number to both sides of an inequality preserves the inequality.
Finset.card_union_of_disjoint- The cardinality of the union of two disjoint finite sets is the sum of their cardinalities.
Finset.mem_singleton_self- An element always belongs to its own singleton set.
Finset.mem_union_right- If an element belongs to t, then it belongs to the union s ∪ t.
Finset.subset_union_left- Every finite set is a subset of its union with another set.
Finset.card_lt_card- A strict subset of a finite set has strictly smaller cardinality.
true_and- The logical conjunction True ∧ p simplifies to p.
Finset.mem_univ- Every element of a finite type belongs to the universal finite set Finset.univ.
Finset.mem_filter- An element belongs to filter p s if and only if it belongs to s and satisfies the predicate p.
Finset.exists_min_image- A nonempty finite set has an element minimizing a given linearly ordered function.
Finset.card_singleton- The cardinality of a singleton finite set is 1.
Finset.empty_subset- The empty set is a subset of every finite set.
Finset.card_eq_zero.mp- If a finite set has cardinality 0, then it is empty.
Fintype.card_eq_zero_iff.mpr- An empty finite type has cardinality 0.
Finset.not_nonempty_iff_eq_empty- A finite set is not nonempty if and only if it is empty.
Finset.card_eq_zero- A finite set has cardinality 0 if and only if it is empty.
Finset.univ_eq_empty_iff.mp- If the universal finite set of a type is empty, then the type is empty.
Finset.eq_empty_or_nonempty- Every finite set is either empty or nonempty.
- In this formalization, `d` denotes the facet size (the number of vertices in each facet), which is 1 plus the standard geometric dimension of a facet.
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.
/-- Dimension formula for simplicial complexes with pairwise disjoint minimal nonfaces. -/theorem disjoint_minimal_nonfaces_dimension {V : Type*} [DecidableEq V] [Fintype V] (Δ : AbstractSimplicialComplex V) (n d s : ℕ) (hn : Fintype.card V = n) (hpure : simplicial_is_pure Δ d) (hconn : (simplicial_dual_graph Δ d).Connected) (M_set : Finset (Finset V)) (hs : M_set.card = s) (hM_all : ∀ M, simplicial_is_minimal_nonface Δ M ↔ M ∈ M_set) (hM_disj : ∀ M₁ ∈ M_set, ∀ M₂ ∈ M_set, M₁ ≠ M₂ → Disjoint M₁ M₂) : d = n - s := by classical -- a facet exists because the dual graph is connected obtain ⟨⟨G, hGfacet⟩⟩ := hconn.nonempty have hGcard : G.card = d := hpure G hGfacet have hGmem : G ∈ Δ.faces := hGfacet.1 have hGmax : ∀ H ∈ Δ.faces, G ⊆ H → G = H := hGfacet.2 -- faces are closed under nonempty subsets have hlower : ∀ {a b : Finset V}, a ∈ Δ.faces → b ⊆ a → b.Nonempty → b ∈ Δ.faces := fun {a b} ha hba hb => (Δ.isRelLowerSet_faces ha).2 hba hb rcases Finset.eq_empty_or_nonempty (Finset.univ : Finset V) with huniv | huniv · -- degenerate case: no vertices have hEmpty : IsEmpty V := Finset.univ_eq_empty_iff.mp huniv have hd0 : d = 0 := by rw [← hGcard, Finset.card_eq_zero, ← Finset.not_nonempty_iff_eq_empty] rintro ⟨x, -⟩ exact hEmpty.false x have hn0 : n = 0 := by rw [← hn] exact Fintype.card_eq_zero_iff.mpr hEmpty have hs0 : s = 0 := by have hMs : M_set = ∅ := by rw [← Finset.not_nonempty_iff_eq_empty] rintro ⟨M, hM⟩ have h2 : 2 ≤ M.card := ((hM_all M).mpr hM).1 have hMe : M = ∅ := by rw [← Finset.not_nonempty_iff_eq_empty] rintro ⟨x, -⟩ exact hEmpty.false x rw [hMe] at h2 simp at h2 rw [← hs, hMs] simp omega · -- main case: `d ≥ 1` because facets are nonempty have hd1 : 1 ≤ d := by have hpos : 0 < G.card := by by_contra h have hz : G.card = 0 := by omega have hGe : G = ∅ := Finset.card_eq_zero.mp hz obtain ⟨v, -⟩ := huniv have hv : ({v} : Finset V) ∈ Δ.faces := Δ.singleton_mem v have hsub : G ⊆ {v} := by rw [hGe]; exact Finset.empty_subset _ have heq : G = {v} := hGmax {v} hv hsub have hc : ({v} : Finset V).card = 0 := by rw [← heq, hGe]; simp rw [Finset.card_singleton] at hc omega omega -- (A) every nonface with at least two vertices contains a minimal nonface have hmin_exists : ∀ N : Finset V, N ∉ Δ.faces → 2 ≤ N.card → ∃ M : Finset V, simplicial_is_minimal_nonface Δ M ∧ M ⊆ N := by intro N hN hN2 have hne : (Finset.univ.filter (fun M : Finset V => M ⊆ N ∧ M ∉ Δ.faces ∧ 2 ≤ M.card)).Nonempty := ⟨N, by simp [hN, hN2]⟩ obtain ⟨M, hMmem, hMmin⟩ := Finset.exists_min_image (Finset.univ.filter (fun M : Finset V => M ⊆ N ∧ M ∉ Δ.faces ∧ 2 ≤ M.card)) (fun M => M.card) hne simp only [Finset.mem_filter, Finset.mem_univ, true_and] at hMmem obtain ⟨hMN, hMnotface, hM2⟩ := hMmem refine ⟨M, ⟨hM2, hMnotface, ?_⟩, hMN⟩ intro T hTM hTne by_contra hTnotface have hT2 : 2 ≤ T.card := by have hpos : 0 < T.card := Finset.card_pos.mpr hTne have hne1 : T.card ≠ 1 := by intro h1 obtain ⟨x, rfl⟩ := Finset.card_eq_one.mp h1 exact hTnotface (Δ.singleton_mem x) omega have hTfilt : T ∈ Finset.univ.filter (fun M : Finset V => M ⊆ N ∧ M ∉ Δ.faces ∧ 2 ≤ M.card) := by simp only [Finset.mem_filter, Finset.mem_univ, true_and] exact ⟨hTM.subset.trans hMN, hTnotface, hT2⟩ have hle := hMmin T hTfilt have hlt : T.card < M.card := Finset.card_lt_card hTM omega -- (B) adding a vertex outside a facet always produces a nonface have hfac_insert : ∀ (H : Finset V) (v : V), simplicial_is_facet Δ H → v ∉ H → H ∪ {v} ∉ Δ.faces := by intro H v hH hv hmem have heq : H = H ∪ {v} := hH.2 _ hmem Finset.subset_union_left have hv1 : v ∈ H ∪ {v} := Finset.mem_union_right H (Finset.mem_singleton_self v) rw [← heq] at hv1 exact hv hv1 -- (C) every vertex outside a facet lies in a minimal nonface contained in -- the facet together with that vertex have hcover : ∀ (H : Finset V) (v : V), simplicial_is_facet Δ H → v ∉ H → ∃ M ∈ M_set, v ∈ M ∧ M ⊆ H ∪ {v} := by intro H v hH hv have hnotface : H ∪ {v} ∉ Δ.faces := hfac_insert H v hH hv have hHcard : H.card = d := hpure H hH have hcard2 : 2 ≤ (H ∪ {v}).card := by have h1 : (H ∪ {v}).card = H.card + 1 := Finset.card_union_of_disjoint (Finset.disjoint_singleton_right.mpr hv) rw [h1, hHcard] exact Nat.add_le_add_right hd1 1 obtain ⟨M, hMmin, hMH⟩ := hmin_exists (H ∪ {v}) hnotface hcard2 have hMmem : M ∈ M_set := (hM_all M).mp hMmin have hM2 : 2 ≤ M.card := hMmin.1 have hMnotface : M ∉ Δ.faces := hMmin.2.1 have hMpos : 0 < M.card := by omega have hMnotsub : ¬ M ⊆ H := fun hsub => hMnotface (hlower hH.1 hsub (Finset.card_pos.mp hMpos)) obtain ⟨x, hxM, hxH⟩ := Finset.not_subset.mp hMnotsub have hx : x ∈ H ∪ {v} := hMH hxM rw [Finset.mem_union] at hx have hvM : v ∈ M := by rcases hx with h | h · exact absurd h hxH · rw [Finset.mem_singleton] at h rw [h] at hxM exact hxM exact ⟨M, hMmem, hvM, hMH⟩ -- (D) each minimal nonface contributes exactly one vertex outside `G` have huniq : ∀ M ∈ M_set, ∃ v : V, M \ G = {v} := by intro M hM have hM2 : 2 ≤ M.card := ((hM_all M).mpr hM).1 have hMnotface : M ∉ Δ.faces := ((hM_all M).mpr hM).2.1 have hMpos : 0 < M.card := by omega have hMnotsub : ¬ M ⊆ G := fun hsub => hMnotface (hlower hGmem hsub (Finset.card_pos.mp hMpos)) obtain ⟨v, hvM, hvG⟩ := Finset.not_subset.mp hMnotsub refine ⟨v, ?_⟩ apply Finset.Subset.antisymm · intro x hx rw [Finset.mem_sdiff] at hx obtain ⟨hxM, hxG⟩ := hx obtain ⟨M', hM', hxM', hM'sub⟩ := hcover G x hGfacet hxG have hM'eq : M' = M := by by_contra hne have hd := hM_disj M' hM' M hM hne exact (Finset.disjoint_left.mp hd) hxM' hxM rw [hM'eq] at hM'sub have hv' : v ∈ G ∪ {x} := hM'sub hvM rw [Finset.mem_union] at hv' rcases hv' with h | h · exact absurd h hvG · rw [Finset.mem_singleton] at h rw [Finset.mem_singleton] exact h.symm · intro x hx rw [Finset.mem_singleton] at hx rw [hx] exact Finset.mem_sdiff.mpr ⟨hvM, hvG⟩ have hcard_one : ∀ M ∈ M_set, (M \ G).card = 1 := by intro M hM obtain ⟨v, hv⟩ := huniq M hM rw [hv, Finset.card_singleton] -- the complement of a facet is the disjoint union of these singletons have hVF : (Finset.univ \ G) = M_set.biUnion (fun M => M \ G) := by apply Finset.Subset.antisymm · intro x hx rw [Finset.mem_sdiff] at hx obtain ⟨-, hxG⟩ := hx obtain ⟨M, hM, hxM, -⟩ := hcover G x hGfacet hxG exact Finset.mem_biUnion.mpr ⟨M, hM, Finset.mem_sdiff.mpr ⟨hxM, hxG⟩⟩ · intro x hx obtain ⟨M, hM, hxM⟩ := Finset.mem_biUnion.mp hx exact Finset.mem_sdiff.mpr ⟨Finset.mem_univ x, (Finset.mem_sdiff.mp hxM).2⟩ have hcardVF : (Finset.univ \ G).card = s := by rw [hVF, Finset.card_biUnion (fun M hM M' hM' hne => (hM_disj M hM M' hM' hne).mono Finset.sdiff_subset Finset.sdiff_subset)] rw [Finset.sum_congr rfl hcard_one] simp [hs] have hsum := Finset.card_sdiff_add_card_eq_card (Finset.subset_univ G) rw [hcardVF, hGcard, Finset.card_univ, hn] at hsum omega