AFTD Auto-Formalizing Theoretical Domains

digraph_semisaturation_bounded_of_isolated_edge

theoremverifiedformalization

Let 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 and digraph_has_isolated_edge G hold. Then the semisaturation function is bounded: there exist C : ℕ and n₀ : ℕ such that for all n ≥ n₀, digraph_ssat n G ≤ C.

Statement

theorem digraph_semisaturation_bounded_of_isolated_edge {V : Type*} [Fintype V] [DecidableEq V] (G : Digraph V) [DecidableRel G.Adj] (hG : digraph_is_oriented G) (he : digraph_has_isolated_edge G) : ∃ C : ℕ, ∃ n₀ : ℕ, ∀ n ≥ n₀, digraph_ssat n G ≤ C
Formalizes
arXiv:2610.18600 Lemma 2.1
Verified
24 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 5
  • digraph_semisaturation_isolated_edge_boundIf G : Digraph V is a finite oriented digraph with DecidableEq V and DecidableRel G.Adj satisfying digraph_is_oriented G and…
  • 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_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_edge_countThe number m of edges (arcs) of a finite digraph G.
  • 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 :…

Read back from the Lean

Let $V$ be a finite type with decidable equality, and let $G$ be a directed graph on $V$ with decidable adjacency relation. Assume that: 1. $G$ is oriented (for all $u, v \in V$, if $u \to v$ in $G$, then $v \not\to u$ in $G$, which also precludes self-loops); 2. $G$ has an isolated directed edge: there exist vertices $u, v \in V$ such that $u \to v$ in $G$, and any vertex incident to $u$ or $v$ (in either direction) must be $u$ or $v$ (meaning the connected component of $\{u, v\}$ contains only the edge $u \to v$). Then there exist natural numbers $C$ and $n_0$ such that for all $n \ge n_0$, the semisaturation number digraph_ssat n G is at most $C$.

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

The theorem asserts that the semisaturation number of any finite oriented digraph G containing an isolated edge is eventually bounded by a constant. The proof directly applies digraph_semisaturation_isolated_edge_bound, which provides an explicit threshold n₀ beyond which digraph_ssat n G ≤ 3 * (|E(G)| - 1). Choosing C = 3 * (|E(G)| - 1) and this threshold n₀ witnesses the required existential bound.

  1. For all n at or beyond an explicit threshold n₀, the semisaturation number digraph_ssat n G is bounded by the constant C = 3 * (|E(G)| - 1).

    Applying digraph_semisaturation_isolated_edge_bound to the oriented digraph G with an isolated edge yields a threshold n₀ such that digraph_ssat n G ≤ 3 * (|E(G)| - 1) for all n ≥ n₀. Choosing the constant bound C = 3 * (|E(G)| - 1) together with this threshold n₀ satisfies the existential statement.

    lines 3–4

    uses digraph_semisaturation_isolated_edge_bound

      obtain ⟨n₀, hn₀⟩ := digraph_semisaturation_isolated_edge_bound G hG he
      exact ⟨3 * (digraph_edge_count G - 1), n₀, hn₀⟩
digraph_semisaturation_isolated_edge_bound
For any finite oriented digraph G with an isolated edge, there exists an integer threshold n₀ such that for all n ≥ n₀, the semisaturation number digraph_ssat n G is at most 3 * (|E(G)| - 1).

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

/-- Bounded semisaturation for oriented graphs containing an isolated edge (Lemma 2.1). -/theorem digraph_semisaturation_bounded_of_isolated_edge {V : Type*} [Fintype V] [DecidableEq V] (G : Digraph V) [DecidableRel G.Adj] (hG : digraph_is_oriented G) (he : digraph_has_isolated_edge G) : ∃ C : ℕ, ∃ n₀ : ℕ, ∀ n ≥ n₀, digraph_ssat n G ≤ C := by  obtain ⟨n₀, hn₀⟩ := digraph_semisaturation_isolated_edge_bound G hG he  exact ⟨3 * (digraph_edge_count G - 1), n₀, hn₀⟩
See it in the graphDiscuss this resultChallenge it