digraph_weighted_center_strict54_certificate
The displayed 54-vertex graph is loopless, oriented, triangle-free and arc-dominated, has minimum outdegree seven and auxiliary independence at most three, and has overlap 18 with exactly 15 common-predecessor pairs of multiplicity two.
Statement
theorem digraph_weighted_center_strict54_certificate : (∀ u, ¬ digraph_weighted_center_strict54_graph.Adj u u) ∧ (∀ u v, digraph_weighted_center_strict54_graph.Adj u v → ¬ digraph_weighted_center_strict54_graph.Adj v u) ∧ (∀ u v w, digraph_weighted_center_strict54_graph.Adj u v → digraph_weighted_center_strict54_graph.Adj v w → ¬ digraph_weighted_center_strict54_graph.Adj w u) ∧ (∀ u v, digraph_weighted_center_strict54_graph.Adj u v → ∃ p, digraph_weighted_center_strict54_graph.Adj p u ∧ digraph_weighted_center_strict54_graph.Adj p v) ∧ (∀ u, 7 ≤ (Finset.univ.filter fun v => digraph_weighted_center_strict54_graph.Adj u v).card) ∧ (digraph_common_predecessor_graph digraph_weighted_center_strict54_graph).IndepSetFree 4 ∧ ((∑ v : Fin 54, Nat.choose (Finset.univ.filter fun w => digraph_weighted_center_strict54_graph.Adj v w).card 2) - (digraph_common_predecessor_graph digraph_weighted_center_strict54_graph).edgeFinset.card) = 18 ∧ digraph_common_predecessor_double_edges (Fin 54) digraph_weighted_center_strict54_graph = 15
- Source
- Strictness witness for the weighted center route; experiments 13477 and 13478.
- Verified
- 04 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 13
- digraph_weighted_center_strict54_graphThe cyclic 53-vertex digraph with steps 1, 8, 14, 16, 28, 32, 33, extended by a new vertex with in-neighbors 0, 1, 17, 25 and…
- digraph_common_predecessor_graphThe simple graph joining distinct vertices that have a common in-neighbor in the digraph.
- digraph_common_predecessor_double_edgesThe number of edges in the common-predecessor graph whose endpoints have exactly two common predecessors.
- digraph_strict54_nonadj_mask_soundTwo distinct vertices whose bit is clear in the nonadjacency mask have a common predecessor.
- digraph_strict54_out_mask_double_countIn the out-mask graph exactly 15 unordered pairs of vertices have exactly two common predecessors.
- digraph_strict54_nonadj_mask_fourThree pairwise nonadjacent vertices of the nonadjacency masks have no common nonneighbour.
- digraph_strict54_adj_iff_out_maskThe out-mask table describes the arcs of the 54-vertex strictness witness exactly.
- digraph_strict54_out_mask_pair_countIn the out-mask graph exactly 1144 unordered pairs of vertices have a common predecessor.
- digraph_strict54_out_maskBit v of the value at u is set exactly when u -> v is an arc of the 54-vertex strictness witness graph.
- LinearOrder.toTotalPreorderEvery
LinearOrderis aTotalPreorder. - digraph_strict54_out_mask_factsThe out-mask graph is loopless, oriented, has no directed triangle, every arc has a common predecessor of its ends, every outdegree is at…
- digraph_strict54_nonadj_maskBit v of the value at u is set exactly when v differs from u and u, v have no common predecessor in the 54-vertex strictness witness graph.
- TotalPreorderA total preorder: a preorder where
≤is total (complete). This is weaker thanLinearOrder— it does NOT require antisymmetry or…
The proof, explained
The 54-vertex directed graph is verified to satisfy all eight properties by translating graph-theoretic predicates into bitwise operations on precomputed integer masks. Local properties—looplessness, asymmetry, triangle-freeness, arc domination, and minimum outdegree at least seven—are verified directly against precomputed bitmask properties. To show the auxiliary common-predecessor graph has independence number at most three, the proof shows that the bitwise AND of the non-adjacency masks of any three independent vertices vanishes, leaving no valid bit for a fourth vertex. Finally, bijections between unordered edges and ordered pairs x < y are used to verify the edge count (1144), the overlap (18), and the number of double edges (15).
Adjacency in the 54-vertex directed graph is decidable. automation
For any two vertices u and v, unfolding the graph definition reveals an explicit boolean condition involving finite modular arithmetic and membership in small explicit finsets, which Lean decides via typeclass inference.
intro u v unfold digraph_weighted_center_strict54_graph infer_instance
Adjacency in the common-predecessor graph is decidable. automation
Adjacency in the common-predecessor graph requires u ≠ v and the existence of a common in-neighbor w. Since the vertex type Fin 54 is finite and digraph adjacency is decidable, the bounded existential quantifier is decidable by typeclass synthesis.
intro u v unfold digraph_common_predecessor_graph infer_instance
The mapping from ordered pairs (x, y) with x < y, x ~ y, and P(s(x, y)) to unordered edges s(x, y) is well-defined.
To count graph edges satisfying P, we set up a bijection via Finset.card_bij using the map (x, y) ↦ s(x, y). We verify that whenever x.1 < x.2 and x.1 ~ x.2 with P holding on the pair, the resulting unordered pair s(x.1, x.2) is indeed an edge in the filtered edge finset.
uses
Finset.card_bij,Finset.mem_filter,Finset.mem_univ,true_and,SimpleGraph.mem_edgeFinset,SimpleGraph.mem_edgeSetsymm apply Finset.card_bij (fun x _ => s(x.1, x.2)) · intro x hx simp only [Finset.mem_filter, Finset.mem_univ, true_and] at hx simp only [Finset.mem_filter, SimpleGraph.mem_edgeFinset, SimpleGraph.mem_edgeSet] exact ⟨hx.2.1, hx.2.2⟩
The map from ordered pairs (x, y) with x < y to unordered edges s(x, y) is injective.
If s(x.1, x.2) = s(y.1, y.2), then either x = y directly by Prod.ext, or x.1 = y.2 and x.2 = y.1. The latter implies y.2 < y.1, which contradicts the hypothesis y.1 < y.2 by the asymmetry of strict inequality (lt_asymm).
uses
Finset.mem_filter,Finset.mem_univ,true_and,Sym2.eq_iff.mp,Prod.ext,lt_asymm· intro x hx y hy hxy simp only [Finset.mem_filter, Finset.mem_univ, true_and] at hx hy rcases Sym2.eq_iff.mp hxy with ⟨h1, h2⟩ | ⟨h1, h2⟩ · exact Prod.ext h1 h2 · exfalso have := hx.1; have := hy.1 rw [h1, h2] at hx exact absurd hx.1 (lt_asymm hy.1)
The map from ordered pairs (x, y) with x < y to unordered edges s(x, y) is surjective.
Every edge in a simple graph has distinct endpoints x ≠ y by looplessness. By trichotomy (lt_or_gt_of_ne), either x < y (giving preimage (x, y)) or y < x (giving preimage (y, x)), with s(y, x) = s(x, y) by Sym2.eq_swap.
uses
Finset.mem_filter,SimpleGraph.mem_edgeFinset,Sym2.ind,SimpleGraph.mem_edgeSet,lt_or_gt_of_ne,Sym2.eq_swap,Finset.mem_univ,true_and· intro e he simp only [Finset.mem_filter, SimpleGraph.mem_edgeFinset] at he obtain ⟨he, hP⟩ := he induction e using Sym2.ind with | _ x y => rw [SimpleGraph.mem_edgeSet] at he rcases lt_or_gt_of_ne (G.ne_of_adj he) with h | h · exact ⟨(x, y), by simp [h, he, hP], rfl⟩ · refine ⟨(y, x), ?_, Sym2.eq_swap⟩ simp only [Finset.mem_filter, Finset.mem_univ, true_and] exact ⟨h, G.adj_symm he, by rw [Sym2.eq_swap]; exact hP⟩
Digraph adjacency, out-neighborhoods, and common-predecessor adjacency are characterized via bitmask operations.
We introduce digraph_strict54_adj_iff_out_mask to identify directed arcs u → v with the v-th bit of out-mask u. We unpack the precomputed facts digraph_strict54_out_mask_facts, rewrite out-neighborhood finsets to bitmask filters (hfilt), and characterize adjacency in the common-predecessor graph as distinct vertices sharing a set bit in some out-mask (hJ).
uses
digraph_strict54_adj_iff_out_mask,digraph_strict54_out_mask_facts,Finset.filter_congrhave hA := digraph_strict54_adj_iff_out_mask obtain ⟨hloop, hor, htri, hdom, hdeg, hch⟩ := digraph_strict54_out_mask_facts have hfilt : ∀ u : Fin 54, (Finset.univ.filter fun v => digraph_weighted_center_strict54_graph.Adj u v) = Finset.univ.filter fun v : Fin 54 => (digraph_strict54_out_mask u.val).testBit v.val = true := fun u => Finset.filter_congr fun v _ => hA u v have hJ : ∀ a b : Fin 54, (digraph_common_predecessor_graph digraph_weighted_center_strict54_graph).Adj a b ↔ a ≠ b ∧ ∃ w : Fin 54, (digraph_strict54_out_mask w.val).testBit a.val = true ∧ (digraph_strict54_out_mask w.val).testBit b.val = true := by intro a b change (a ≠ b ∧ ∃ w, digraph_weighted_center_strict54_graph.Adj w a ∧ digraph_weighted_center_strict54_graph.Adj w b) ↔ _ simp only [hA]
Non-adjacency in the common-predecessor graph implies the corresponding bit in the non-adjacency mask is true.
For distinct vertices a ≠ b that do not share a common predecessor, we prove that bit b of nonadj_mask(a) is true. If it were false, digraph_strict54_nonadj_mask_sound would produce a common predecessor, contradicting non-adjacency in the common-predecessor graph.
uses
Bool.not_eq_true,digraph_strict54_nonadj_mask_soundhave hJbit : ∀ a b : Fin 54, a ≠ b → ¬ (digraph_common_predecessor_graph digraph_weighted_center_strict54_graph).Adj a b → (digraph_strict54_nonadj_mask a.val).testBit b.val = true := by intro a b hab hn by_contra hb rw [Bool.not_eq_true] at hb exact hn ((hJ a b).mpr ⟨hab, digraph_strict54_nonadj_mask_sound a b hab hb⟩)
The common-predecessor graph has exactly 1144 edges.
Using in522_edge_card with P = True, the number of edges equals the number of ordered pairs x < y adjacent in the common-predecessor graph. By hJ and Finset.filter_congr, this matches the precomputed count digraph_strict54_out_mask_pair_count, which is 1144.
uses
in522_edge_card,Finset.filter_true_of_mem,congrArg,digraph_strict54_out_mask_pair_count,Finset.filter_congr,ne_of_lthave hEdges : (digraph_common_predecessor_graph digraph_weighted_center_strict54_graph).edgeFinset.card = 1144 := by have h := in522_edge_card (digraph_common_predecessor_graph digraph_weighted_center_strict54_graph) (fun _ => True) rw [Finset.filter_true_of_mem (fun _ _ => trivial)] at h rw [h] refine (congrArg Finset.card ?_).trans digraph_strict54_out_mask_pair_count apply Finset.filter_congr intro x _ rw [hJ] exact ⟨fun h => ⟨h.1, h.2.1.2⟩, fun h => ⟨h.1, ⟨ne_of_lt h.1, h.2⟩, trivial⟩⟩
The digraph is loopless, oriented, triangle-free, arc-dominated, and has minimum outdegree at least 7.
We split the goal using refine and prove each local property from the corresponding precomputed bitmask fact: no self-loops by hloop, asymmetry by hor, triangle-freeness by htri, arc domination by hdom, and minimum outdegree at least 7 by hdeg via the out-neighborhood equivalence hfilt.
uses
Bool.false_ne_truerefine ⟨fun u h => ?_, fun u v h1 h2 => ?_, fun u v w h1 h2 h3 => ?_, fun u v h => ?_, fun u => ?_, ?_, ?_, ?_⟩ · rw [hA, hloop u] at h; exact Bool.false_ne_true h · rw [hA] at h1 h2; rw [hor u v h1] at h2; exact Bool.false_ne_true h2 · rw [hA] at h1 h2 h3; rw [htri u v h1 w h2] at h3; exact Bool.false_ne_true h3 · rw [hA] at h obtain ⟨p, hp1, hp2⟩ := hdom u v h exact ⟨p, (hA p u).mpr hp1, (hA p v).mpr hp2⟩ · rw [hfilt]; exact hdeg u
The common-predecessor graph contains no independent set of size 4.
Suppose an independent set of size 4 exists: t = {a, b, c, d}. By independence, all pairs are non-adjacent, so each pair has its non-adjacency bit set. Lemma digraph_strict54_nonadj_mask_four proves that the bitwise AND of the masks of a, b, and c is zero. But d is non-adjacent to all three, so bit d of this bitwise AND must be true, which contradicts testing bit d of zero.
uses
Finset.card_eq_succ.mp,Finset.card_eq_three.mp,Finset.mem_insert,Finset.mem_singleton,not_or,digraph_strict54_nonadj_mask_four,Nat.testBit_and,Bool.and_eq_true,Nat.zero_testBit,Bool.false_ne_true· intro t ht obtain ⟨hind, hcard⟩ := ht obtain ⟨a, s, ha, rfl, hs⟩ := Finset.card_eq_succ.mp hcard obtain ⟨b, c, d, hbc, hbd, hcd, rfl⟩ := Finset.card_eq_three.mp hs simp only [Finset.mem_insert, Finset.mem_singleton, not_or] at ha obtain ⟨hab, hac, had⟩ := ha have hn : ∀ x y : Fin 54, x ∈ ({a, b, c, d} : Finset (Fin 54)) → y ∈ ({a, b, c, d} : Finset (Fin 54)) → x ≠ y → (digraph_strict54_nonadj_mask x.val).testBit y.val = true := by intro x y hx hy hxy exact hJbit x y hxy (hind (by exact_mod_cast hx) (by exact_mod_cast hy) hxy) have h0 := digraph_strict54_nonadj_mask_four a b c (hn a b (by simp) (by simp) hab) (hn a c (by simp) (by simp) hac) (hn b c (by simp) (by simp) hbc) have h1 : (digraph_strict54_nonadj_mask a.val &&& digraph_strict54_nonadj_mask b.val &&& digraph_strict54_nonadj_mask c.val).testBit d.val = true := by simp only [Nat.testBit_and, Bool.and_eq_true] exact ⟨⟨hn a d (by simp) (by simp) had, hn b d (by simp) (by simp) hbd⟩, hn c d (by simp) (by simp) hcd⟩ rw [h0, Nat.zero_testBit] at h1 exact Bool.false_ne_true h1
The overlap of common predecessors is 18. automation
Simplification with hfilt rewrites the sum of binomial coefficients of outdegrees to 1162 (hch). Subtracting the number of edges of the common-predecessor graph (1144, from hEdges) yields 1162 - 1144 = 18.
· simp only [hfilt, hch, hEdges]There are exactly 15 pairs of vertices that share exactly two common predecessors.
Unfolding digraph_common_predecessor_double_edges, we apply in522_edge_card to count pairs as ordered pairs x < y with two predecessors. We show that common predecessors correspond to vertices whose out-masks have both bits x.1 and x.2 set, matching the precomputed count digraph_strict54_out_mask_double_count = 15.
uses
in522_edge_card,congrArg,digraph_strict54_out_mask_double_count,Finset.filter_congr,Sym2.mem_iff,forall_eq_or_imp,forall_eq,Finset.mem_filter,Finset.mem_univ,true_and,ne_of_lt· unfold digraph_common_predecessor_double_edges rw [in522_edge_card] refine (congrArg Finset.card ?_).trans digraph_strict54_out_mask_double_count apply Finset.filter_congr intro x _ have hc : ∀ y : Fin 54, (∀ z, z ∈ s(x.1, x.2) → digraph_weighted_center_strict54_graph.Adj y z) ↔ ((digraph_strict54_out_mask y.val).testBit x.1.val = true ∧ (digraph_strict54_out_mask y.val).testBit x.2.val = true) := by intro y simp only [Sym2.mem_iff, forall_eq_or_imp, forall_eq, hA] have hcard : ∀ (inst : DecidablePred fun p => ∀ z ∈ s(x.1, x.2), digraph_weighted_center_strict54_graph.Adj p z), (@Finset.filter _ _ inst Finset.univ).card = (Finset.univ.filter fun p : Fin 54 => (digraph_strict54_out_mask p.val).testBit x.1.val = true ∧ (digraph_strict54_out_mask p.val).testBit x.2.val = true).card := by intro inst refine congrArg Finset.card ?_ ext y simp only [Finset.mem_filter, Finset.mem_univ, true_and] exact hc y rw [hcard, hJ] constructor · rintro ⟨h1, ⟨_, h2⟩, h3⟩; exact ⟨h1, h2, h3⟩ · rintro ⟨h1, h2, h3⟩; exact ⟨h1, ⟨ne_of_lt h1, h2⟩, h3⟩
Finset.card_bij- Two finite sets have the same cardinality if there is a bijection between them (a map that is well-defined, injective, and surjective).
Finset.mem_filter- An element belongs to a filtered finset if and only if it belongs to the ambient finset and satisfies the filtering predicate.
Finset.mem_univ- Every element of a finite type belongs to the universal finset Finset.univ.
true_and- The conjunction of True with any proposition p is logically equivalent to p.
SimpleGraph.mem_edgeFinset- An unordered pair belongs to a simple graph's edge finset if and only if it belongs to its edge set.
SimpleGraph.mem_edgeSet- The unordered pair s(v, w) is in the edge set of G if and only if v and w are adjacent in G.
Sym2.eq_iff.mp- Equality of unordered pairs s(a, b) = s(c, d) implies (a = c and b = d) or (a = d and b = c).
Prod.ext- Two ordered pairs are equal if and only if their first components are equal and their second components are equal.
lt_asymm- Strict inequality is asymmetric: if a < b, then b < a is false.
Sym2.ind- Every element of the symmetric square Sym2 α is of the form s(x, y) for some x, y in α.
lt_or_gt_of_ne- In a linear order, two distinct elements satisfy either a < b or b < a.
Sym2.eq_swap- An unordered pair is symmetric in its components: s(a, b) = s(b, a).
digraph_strict54_adj_iff_out_mask- Vertex u has a directed edge to vertex v in the 54-vertex graph if and only if bit v of the out-mask of u is true.
digraph_strict54_out_mask_facts- Precomputed bitmask facts: the masks have no self-bits, are oriented, contain no directed triangles, satisfy arc domination, have outdegree at least 7, and have binomial coefficient sum 1162.
Finset.filter_congr- If two predicates agree on every element of a finset, then filtering the finset by either predicate produces the same result.
Bool.not_eq_true- For a boolean b, not (b = true) is equivalent to b = false.
digraph_strict54_nonadj_mask_sound- If two distinct vertices have bit b false in the non-adjacency mask of a, then they share a common predecessor.
in522_edge_card- The number of edges of a graph on Fin n satisfying predicate P equals the number of ordered pairs (x, y) with x < y, G.Adj x y, and P(s(x, y)).
Finset.filter_true_of_mem- Filtering a finset by a predicate that holds for all of its elements returns the original finset unchanged.
congrArg- If two inputs are equal, applying a function to them yields equal outputs.
digraph_strict54_out_mask_pair_count- The number of ordered pairs x < y in Fin 54 that share a predecessor in the precomputed out-masks is 1144.
ne_of_lt- If a < b in a preorder, then a ≠ b.
Bool.false_ne_true- The boolean values false and true are distinct.
Finset.card_eq_succ.mp- A finset of cardinality k + 1 can be decomposed as {a} ∪ t with a ∉ t and |t| = k.
Finset.card_eq_three.mp- A finset has cardinality 3 if and only if it consists of three pairwise distinct elements.
Finset.mem_insert- An element belongs to insert b s if and only if it equals b or belongs to s.
Finset.mem_singleton- An element belongs to the singleton {a} if and only if it equals a.
not_or- De Morgan's law: not (p or q) is equivalent to (not p) and (not q).
digraph_strict54_nonadj_mask_four- The bitwise AND of the non-adjacency masks of any three pairwise non-adjacent vertices is zero.
Nat.testBit_and- The i-th bit of a bitwise AND x &&& y is the boolean AND of the i-th bit of x and the i-th bit of y.
Bool.and_eq_true- A boolean AND a && b equals true if and only if both a and b equal true.
Nat.zero_testBit- Every bit of the natural number zero is false.
digraph_strict54_out_mask_double_count- The number of pairs x < y in Fin 54 that have exactly two common predecessors in the out-masks is 15.
Sym2.mem_iff- An element belongs to the unordered pair s(b, c) if and only if it equals b or equals c.
forall_eq_or_imp- A universal quantification over a = a' ∨ Q a is equivalent to holding at a' and holding for all a satisfying Q a.
forall_eq- A universal quantification ∀ a, a = a' → p a simplifies to p a'.
- The graph certificate relies on precomputed bitmask representations whose global properties (such as edge count 1144, binomial sum 1162, double-edge count 15, and the bitwise AND vanishing on triples of non-adjacent vertices) were verified computationally in advance.
- Edge counting in the simple graph is formally proved via a bijection with ordered pairs (x, y) satisfying x < y, turning unordered edge membership into a computable condition on ordered pairs.
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.
private instance in516_strict54_adj : DecidableRel digraph_weighted_center_strict54_graph.Adj := by intro u v unfold digraph_weighted_center_strict54_graph infer_instanceprivate instance in516_strict54_common_adj : DecidableRel (digraph_common_predecessor_graph digraph_weighted_center_strict54_graph).Adj := by intro u v unfold digraph_common_predecessor_graph infer_instanceprivate theorem in522_edge_card {n : ℕ} (G : SimpleGraph (Fin n)) [Fintype G.edgeSet] (P : Sym2 (Fin n) → Prop) [DecidablePred P] [DecidableRel G.Adj] : (G.edgeFinset.filter P).card = ((Finset.univ : Finset (Fin n × Fin n)).filter fun x => x.1 < x.2 ∧ G.Adj x.1 x.2 ∧ P s(x.1, x.2)).card := by symm apply Finset.card_bij (fun x _ => s(x.1, x.2)) · intro x hx simp only [Finset.mem_filter, Finset.mem_univ, true_and] at hx simp only [Finset.mem_filter, SimpleGraph.mem_edgeFinset, SimpleGraph.mem_edgeSet] exact ⟨hx.2.1, hx.2.2⟩ · intro x hx y hy hxy simp only [Finset.mem_filter, Finset.mem_univ, true_and] at hx hy rcases Sym2.eq_iff.mp hxy with ⟨h1, h2⟩ | ⟨h1, h2⟩ · exact Prod.ext h1 h2 · exfalso have := hx.1; have := hy.1 rw [h1, h2] at hx exact absurd hx.1 (lt_asymm hy.1) · intro e he simp only [Finset.mem_filter, SimpleGraph.mem_edgeFinset] at he obtain ⟨he, hP⟩ := he induction e using Sym2.ind with | _ x y => rw [SimpleGraph.mem_edgeSet] at he rcases lt_or_gt_of_ne (G.ne_of_adj he) with h | h · exact ⟨(x, y), by simp [h, he, hP], rfl⟩ · refine ⟨(y, x), ?_, Sym2.eq_swap⟩ simp only [Finset.mem_filter, Finset.mem_univ, true_and] exact ⟨h, G.adj_symm he, by rw [Sym2.eq_swap]; exact hP⟩theorem digraph_weighted_center_strict54_certificate : (∀ u, ¬ digraph_weighted_center_strict54_graph.Adj u u) ∧ (∀ u v, digraph_weighted_center_strict54_graph.Adj u v → ¬ digraph_weighted_center_strict54_graph.Adj v u) ∧ (∀ u v w, digraph_weighted_center_strict54_graph.Adj u v → digraph_weighted_center_strict54_graph.Adj v w → ¬ digraph_weighted_center_strict54_graph.Adj w u) ∧ (∀ u v, digraph_weighted_center_strict54_graph.Adj u v → ∃ p, digraph_weighted_center_strict54_graph.Adj p u ∧ digraph_weighted_center_strict54_graph.Adj p v) ∧ (∀ u, 7 ≤ (Finset.univ.filter fun v => digraph_weighted_center_strict54_graph.Adj u v).card) ∧ (digraph_common_predecessor_graph digraph_weighted_center_strict54_graph).IndepSetFree 4 ∧ ((∑ v : Fin 54, Nat.choose (Finset.univ.filter fun w => digraph_weighted_center_strict54_graph.Adj v w).card 2) - (digraph_common_predecessor_graph digraph_weighted_center_strict54_graph).edgeFinset.card) = 18 ∧ digraph_common_predecessor_double_edges (Fin 54) digraph_weighted_center_strict54_graph = 15 := by have hA := digraph_strict54_adj_iff_out_mask obtain ⟨hloop, hor, htri, hdom, hdeg, hch⟩ := digraph_strict54_out_mask_facts have hfilt : ∀ u : Fin 54, (Finset.univ.filter fun v => digraph_weighted_center_strict54_graph.Adj u v) = Finset.univ.filter fun v : Fin 54 => (digraph_strict54_out_mask u.val).testBit v.val = true := fun u => Finset.filter_congr fun v _ => hA u v have hJ : ∀ a b : Fin 54, (digraph_common_predecessor_graph digraph_weighted_center_strict54_graph).Adj a b ↔ a ≠ b ∧ ∃ w : Fin 54, (digraph_strict54_out_mask w.val).testBit a.val = true ∧ (digraph_strict54_out_mask w.val).testBit b.val = true := by intro a b change (a ≠ b ∧ ∃ w, digraph_weighted_center_strict54_graph.Adj w a ∧ digraph_weighted_center_strict54_graph.Adj w b) ↔ _ simp only [hA] have hJbit : ∀ a b : Fin 54, a ≠ b → ¬ (digraph_common_predecessor_graph digraph_weighted_center_strict54_graph).Adj a b → (digraph_strict54_nonadj_mask a.val).testBit b.val = true := by intro a b hab hn by_contra hb rw [Bool.not_eq_true] at hb exact hn ((hJ a b).mpr ⟨hab, digraph_strict54_nonadj_mask_sound a b hab hb⟩) have hEdges : (digraph_common_predecessor_graph digraph_weighted_center_strict54_graph).edgeFinset.card = 1144 := by have h := in522_edge_card (digraph_common_predecessor_graph digraph_weighted_center_strict54_graph) (fun _ => True) rw [Finset.filter_true_of_mem (fun _ _ => trivial)] at h rw [h] refine (congrArg Finset.card ?_).trans digraph_strict54_out_mask_pair_count apply Finset.filter_congr intro x _ rw [hJ] exact ⟨fun h => ⟨h.1, h.2.1.2⟩, fun h => ⟨h.1, ⟨ne_of_lt h.1, h.2⟩, trivial⟩⟩ refine ⟨fun u h => ?_, fun u v h1 h2 => ?_, fun u v w h1 h2 h3 => ?_, fun u v h => ?_, fun u => ?_, ?_, ?_, ?_⟩ · rw [hA, hloop u] at h; exact Bool.false_ne_true h · rw [hA] at h1 h2; rw [hor u v h1] at h2; exact Bool.false_ne_true h2 · rw [hA] at h1 h2 h3; rw [htri u v h1 w h2] at h3; exact Bool.false_ne_true h3 · rw [hA] at h obtain ⟨p, hp1, hp2⟩ := hdom u v h exact ⟨p, (hA p u).mpr hp1, (hA p v).mpr hp2⟩ · rw [hfilt]; exact hdeg u · intro t ht obtain ⟨hind, hcard⟩ := ht obtain ⟨a, s, ha, rfl, hs⟩ := Finset.card_eq_succ.mp hcard obtain ⟨b, c, d, hbc, hbd, hcd, rfl⟩ := Finset.card_eq_three.mp hs simp only [Finset.mem_insert, Finset.mem_singleton, not_or] at ha obtain ⟨hab, hac, had⟩ := ha have hn : ∀ x y : Fin 54, x ∈ ({a, b, c, d} : Finset (Fin 54)) → y ∈ ({a, b, c, d} : Finset (Fin 54)) → x ≠ y → (digraph_strict54_nonadj_mask x.val).testBit y.val = true := by intro x y hx hy hxy exact hJbit x y hxy (hind (by exact_mod_cast hx) (by exact_mod_cast hy) hxy) have h0 := digraph_strict54_nonadj_mask_four a b c (hn a b (by simp) (by simp) hab) (hn a c (by simp) (by simp) hac) (hn b c (by simp) (by simp) hbc) have h1 : (digraph_strict54_nonadj_mask a.val &&& digraph_strict54_nonadj_mask b.val &&& digraph_strict54_nonadj_mask c.val).testBit d.val = true := by simp only [Nat.testBit_and, Bool.and_eq_true] exact ⟨⟨hn a d (by simp) (by simp) had, hn b d (by simp) (by simp) hbd⟩, hn c d (by simp) (by simp) hcd⟩ rw [h0, Nat.zero_testBit] at h1 exact Bool.false_ne_true h1 · simp only [hfilt, hch, hEdges] · unfold digraph_common_predecessor_double_edges rw [in522_edge_card] refine (congrArg Finset.card ?_).trans digraph_strict54_out_mask_double_count apply Finset.filter_congr intro x _ have hc : ∀ y : Fin 54, (∀ z, z ∈ s(x.1, x.2) → digraph_weighted_center_strict54_graph.Adj y z) ↔ ((digraph_strict54_out_mask y.val).testBit x.1.val = true ∧ (digraph_strict54_out_mask y.val).testBit x.2.val = true) := by intro y simp only [Sym2.mem_iff, forall_eq_or_imp, forall_eq, hA] have hcard : ∀ (inst : DecidablePred fun p => ∀ z ∈ s(x.1, x.2), digraph_weighted_center_strict54_graph.Adj p z), (@Finset.filter _ _ inst Finset.univ).card = (Finset.univ.filter fun p : Fin 54 => (digraph_strict54_out_mask p.val).testBit x.1.val = true ∧ (digraph_strict54_out_mask p.val).testBit x.2.val = true).card := by intro inst refine congrArg Finset.card ?_ ext y simp only [Finset.mem_filter, Finset.mem_univ, true_and] exact hc y rw [hcard, hJ] constructor · rintro ⟨h1, ⟨_, h2⟩, h3⟩; exact ⟨h1, h2, h3⟩ · rintro ⟨h1, h2, h3⟩; exact ⟨h1, ⟨ne_of_lt h1, h2⟩, h3⟩