AFTD Auto-Formalizing Theoretical Domains

digraph_seven_two_overlap_order_ge_43

theoremverified

A finite digraph with every outdegree at least seven and twice its common-predecessor overlap below its order has at least 43 vertices.

Statement

theorem digraph_seven_two_overlap_order_ge_43
    (α : Type) [Fintype α] [DecidableEq α] (D : Digraph α) [DecidableRel D.Adj]
    (hdeg : ∀ v, 7 ≤ (Finset.univ.filter fun w => D.Adj v w).card)
    (hsmall : 2 * ((∑ v : α, Nat.choose (Finset.univ.filter fun w => D.Adj v w).card 2) -
      (digraph_common_predecessor_graph D).edgeFinset.card) < Fintype.card α) :
    43 ≤ Fintype.card α
Source
Order constraint for restricted small-overlap searches in the OP-110 campaign.
Verified
04 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2

The proof, explained

The proof shows by contradiction that a finite digraph satisfying the outdegree and overlap hypotheses must have order n at least 43. Since every vertex has outdegree at least 7, the sum of pairs of out-neighbors S = ∑_v choose(d⁺(v), 2) is at least 21 * n. The overlap hypothesis 2 * (S - E) < n then implies that the edge count E of the common-predecessor graph satisfies 41 * n < 2 * E. On the other hand, since this graph is simple on n vertices, 2 * E ≤ 2 * choose(n, 2) ≤ n * (n - 1). If n ≤ 42, then n * (n - 1) ≤ 41 * n, contradicting 41 * n < 2 * E ≤ n * (n - 1).

  1. Adjacency in the common-predecessor graph is decidable.

    Given vertices u and v, unfolding `digraph_common_predecessor_graph` expresses adjacency as u ≠ v together with the existence of a common predecessor w. Because the vertex type is finite with decidable equality and digraph adjacency is decidable, typeclass inference (`infer_instance`) provides the decision procedure.

    lines 3–5

      intro u v
      unfold digraph_common_predecessor_graph
      infer_instance
  2. Letting n = |α|, S = ∑_v choose(d⁺(v), 2), and E be the edge count of the common-predecessor graph, we have E ≤ S.

    We introduce names for the order n = |α|, the sum S of pairs of out-neighbors, and the number of edges E in the common-predecessor graph. The inequality E ≤ S holds by `digraph_common_predecessor_edge_le_sum_choose`, reflecting that every edge in the common-predecessor graph arises from at least one pair of outgoing edges sharing a vertex.

    lines 13–17

    uses digraph_common_predecessor_edge_le_sum_choose

      classical
      let n := Fintype.card α
      let S := ∑ v : α, Nat.choose (Finset.univ.filter fun w => D.Adj v w).card 2
      let E := (digraph_common_predecessor_graph D).edgeFinset.card
      have hES : E ≤ S := digraph_common_predecessor_edge_le_sum_choose α D
  3. 21 * n ≤ S.

    We express 21 * n as the sum of 21 over all n vertices using commutativity of multiplication (`Nat.mul_comm`). By hypothesis `hdeg`, every outdegree is at least 7, so monotonicity of binomial coefficients (`Nat.choose_le_choose`) gives choose(7, 2) ≤ choose(d⁺(v), 2). Since choose(7, 2) = 21, summing these inequalities over all vertices via `Finset.sum_le_sum` establishes 21 * n ≤ S.

    lines 18–28

    uses Nat.mul_comm, Finset.sum_le_sum, Nat.choose_le_choose

      have hS : 21 * n ≤ S := by
        change 21 * Fintype.card α ≤ ∑ v : α,
          Nat.choose (Finset.univ.filter fun w => D.Adj v w).card 2
        calc
          21 * Fintype.card α = ∑ _v : α, 21 := by simp [Nat.mul_comm]
          _ ≤ _ := by
            apply Finset.sum_le_sum
            intro v _
            have h := Nat.choose_le_choose 2 (hdeg v)
            norm_num at h
            exact h
  4. E ≤ choose(n, 2).

    The common-predecessor graph is a simple graph on n vertices, so by `card_edgeFinset_le_card_choose_two`, its number of edges E cannot exceed choose(n, 2).

    lines 29–30

    uses card_edgeFinset_le_card_choose_two

      have hE : E ≤ Nat.choose n 2 :=
        (digraph_common_predecessor_graph D).card_edgeFinset_le_card_choose_two
  5. 41 * n < 2 * E. automation

    The hypothesis `hsmall` states that 2 * (S - E) < n. Combining this with 21 * n ≤ S, linear arithmetic over the natural numbers shows that 42 * n - 2 * E ≤ 2 * (S - E) < n, whence 41 * n < 2 * E, as verified by `omega`.

    lines 31–32

      have hsmall' : 2 * (S - E) < n := hsmall
      have hlin : 41 * n < 2 * E := by omega
  6. 2 * E ≤ n * (n - 1). automation

    Rewriting choose(n, 2) as n * (n - 1) / 2 using `Nat.choose_two_right`, the property `Nat.div_mul_le_self` shows that 2 * choose(n, 2) ≤ n * (n - 1). Combining this with E ≤ choose(n, 2), `omega` concludes that 2 * E ≤ n * (n - 1).

    lines 33–37

    uses Nat.choose_two_right, Nat.div_mul_le_self

      have hchoose : 2 * Nat.choose n 2 ≤ n * (n - 1) := by
        rw [Nat.choose_two_right]
        have h := Nat.div_mul_le_self (n * (n - 1)) 2
        omega
      have hbound : 2 * E ≤ n * (n - 1) := by omega
  7. 43 ≤ n, completing the proof. automation

    Suppose for contradiction that n < 43, so n - 1 ≤ 41 by `omega`. Multiplying both sides by n via `Nat.mul_le_mul_left` and commuting factors with `Nat.mul_comm` gives n * (n - 1) ≤ 41 * n. But we already established 41 * n < 2 * E ≤ n * (n - 1), which contradicts n * (n - 1) ≤ 41 * n. The `omega` tactic detects this contradiction and closes the goal.

    lines 38–42

    uses Nat.mul_comm, Nat.mul_le_mul_left

      by_contra hn
      have hsub : n - 1 ≤ 41 := by omega
      have hmul : n * (n - 1) ≤ 41 * n := by
        simpa [Nat.mul_comm] using Nat.mul_le_mul_left n hsub
      omega
digraph_common_predecessor_edge_le_sum_choose
In any finite digraph, the number of edges in the common-predecessor graph is at most the sum over all vertices v of the binomial coefficient choose(d⁺(v), 2).
Nat.mul_comm
Multiplication of natural numbers is commutative: n * m = m * n.
Finset.sum_le_sum
If f(i) ≤ g(i) for all elements i in a finite set s, then the sum of f over s is at most the sum of g over s.
Nat.choose_le_choose
For a fixed lower index c, the binomial coefficient choose(a, c) is a monotone non-decreasing function of the upper index a.
card_edgeFinset_le_card_choose_two
The number of edges in any finite simple graph on vertex set V is at most choose(|V|, 2).
Nat.choose_two_right
For any natural number n, the binomial coefficient choose(n, 2) equals n * (n - 1) / 2.
Nat.div_mul_le_self
Integer division satisfies (m / n) * n ≤ m for all natural numbers m and n.
Nat.mul_le_mul_left
If n ≤ m, then k * n ≤ k * m for any natural number k.

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

private instance in504_order_decAdj {α : Type} [Fintype α] [DecidableEq α] (D : Digraph α)    [DecidableRel D.Adj] : DecidableRel (digraph_common_predecessor_graph D).Adj := by  intro u v  unfold digraph_common_predecessor_graph  infer_instancetheorem digraph_seven_two_overlap_order_ge_43    (α : Type) [Fintype α] [DecidableEq α] (D : Digraph α) [DecidableRel D.Adj]    (hdeg : ∀ v, 7 ≤ (Finset.univ.filter fun w => D.Adj v w).card)    (hsmall : 2 * ((∑ v : α, Nat.choose (Finset.univ.filter fun w => D.Adj v w).card 2) -      (digraph_common_predecessor_graph D).edgeFinset.card) < Fintype.card α) :    43 ≤ Fintype.card α := by  classical  let n := Fintype.card α  let S := ∑ v : α, Nat.choose (Finset.univ.filter fun w => D.Adj v w).card 2  let E := (digraph_common_predecessor_graph D).edgeFinset.card  have hES : E ≤ S := digraph_common_predecessor_edge_le_sum_choose α D  have hS : 21 * n ≤ S := by    change 21 * Fintype.card α ≤ ∑ v : α,      Nat.choose (Finset.univ.filter fun w => D.Adj v w).card 2    calc      21 * Fintype.card α = ∑ _v : α, 21 := by simp [Nat.mul_comm]      _ ≤ _ := by        apply Finset.sum_le_sum        intro v _        have h := Nat.choose_le_choose 2 (hdeg v)        norm_num at h        exact h  have hE : E ≤ Nat.choose n 2 :=    (digraph_common_predecessor_graph D).card_edgeFinset_le_card_choose_two  have hsmall' : 2 * (S - E) < n := hsmall  have hlin : 41 * n < 2 * E := by omega  have hchoose : 2 * Nat.choose n 2 ≤ n * (n - 1) := by    rw [Nat.choose_two_right]    have h := Nat.div_mul_le_self (n * (n - 1)) 2    omega  have hbound : 2 * E ≤ n * (n - 1) := by omega  by_contra hn  have hsub : n - 1 ≤ 41 := by omega  have hmul : n * (n - 1) ≤ 41 * n := by    simpa [Nat.mul_comm] using Nat.mul_le_mul_left n hsub  omega
See it in the graphDiscuss this resultChallenge it