Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Bridge: the graph-theoretic domination number of `Mathlib`'s `pathGraph n`

Proved
dominationNumber_pathGraph

by raver1975 · Sep 13, 2026 · Mathlib c5ea003 (Lean v4.30.0)

aether-catalognovelty

Bridge: the graph-theoretic domination number of Mathlib's pathGraph n coincides with the combinatorial gammaPath n.

theorem dominationNumber_pathGraph(n : ℕ) :
    dominationNumber (pathGraph n) = gammaPath n := by sorry

Formalization Note Transplanted verbatim from the Aether Catalog source Novelty/TransmissionDominationTree.lean; the statement is byte-identical to the source declaration, elaborated with autoImplicit disabled in the platform environment.

Preamble
-- Thm stub generated from Novelty/TransmissionDominationTree.lean
import Mathlib
import Definitions.Def_Novelty_TransmissionDominationTree

/-!
# Domination number of paths (and the transmission–zero-forcing / domination program)

This file is the first research cycle on the direction

> *Transmission Zero Forcing Number Equals Domination Number on Trees.*

The deepest *fully verified* contribution here is an exact, closed-form evaluation of the
**domination number of the path graph** `P_n` (which is the simplest infinite family of
trees):

  `γ(P_n) = ⌈n/3⌉ = (n + 2) / 3`   (natural-number division).

We give two equivalent developments and connect them:

* a self-contained **combinatorial** model `DominatesPath` / `gammaPath` on `ℕ`, where the
  domination number of `P_n` is computed exactly (`gammaPath_eq`);
* a **genuine graph-theoretic** definition `IsDominatingSet` / `dominationNumber` for an
  arbitrary `SimpleGraph`, together with a card-preserving bridge proving that the
  graph domination number of `Mathlib`'s `SimpleGraph.pathGraph n` equals the combinatorial
  `gammaPath n` (`dominationNumber_pathGraph`), hence equals `(n+2)/3`
  (`dominationNumber_pathGraph_eq`).

The `dominationNumber` definition is stated for general finite graphs so that future cycles
can reuse it for stars, caterpillars, spiders and general trees.

-- !-- Lab Notes -- !--
## Hypothesis
The mission conjecture is `ξ_T(T) = γ(T)` for every tree `T`, where `ξ_T` is a
"transmission zero forcing number".  Ordinary zero forcing fails this badly
(`Z(P_n) = 1` but `γ(P_n) = ⌈n/3⌉`), so any equality must use a *transmission-weighted*
variant.  The first scientific task is therefore to pin down `γ` itself exactly on the
canonical tree family, which is what this file does rigorously.

## Experimental outcome (see ComputationalEvidence.md)
Brute-force enumeration over `P_1 … P_9` confirms `γ(P_n) = ⌈n/3⌉ = 1,1,1,2,2,2,3,3,3`.
The same enumeration shows ordinary `Z(P_n) = 1` for all `n`, decisively separating ordinary
zero forcing from domination and motivating the "transmission" weighting in the conjecture.

## Insights
* The lower bound is a pure *closed-neighbourhood counting* argument: in a path every closed
  neighbourhood has at most `3` vertices, so a dominating set `S` satisfies `n ≤ 3·|S|`.
  This is exactly the `Δ`-degree bound `γ(G) ≥ n/(Δ+1)` specialised to `Δ = 2`, and it is the
  reusable kernel for the general tree program (`lower_bound`).
* The upper bound needs only the *existence* of a small dominating set, not its exact size:
  placing a guard at `min(3k+1, n-1)` for `k < ⌈n/3⌉` dominates everything, and
  `Finset.card_image_le` caps the cardinality without any injectivity bookkeeping
  (`dominates_construction`, `card_construction`).
* Encoding distance-≤1 as `i ≤ s+1 ∧ s ≤ i+1` over `ℕ` lets `omega` discharge every
  metric obligation, including the Euclidean-division case split `3k ≤ i ≤ 3k+2`.

## Failure analysis
* Working directly in `Fin n` makes the counting argument painful (wrap-around `s-1`,
  `Fin`-valued `Finset.Icc`).  Proving the value over `ℕ` and then *bridging* to
  `SimpleGraph.pathGraph` via `Finset.attachFin` / `Finset.image Fin.val` is dramatically
  cleaner and keeps `omega` in charge.
* `omega` does not reduce `(⟨i, hi⟩ : Fin n).val` to `i` by itself; an empty `simp only []`
  (projection reduction) before `omega` is load-bearing in the bridge lemmas.
-/

open Finset SimpleGraph

/-! ## Combinatorial model of domination on the path `P_n` -/










/-! ## Genuine graph-theoretic domination number, and the bridge to `pathGraph` -/
Formal statement
theorem dominationNumber_pathGraph(n : ℕ) :
    dominationNumber (pathGraph n) = gammaPath n := by sorry
Source
https://github.com/paulklemstine/Lean/blob/53c2925a02/Catalog/Novelty/TransmissionDominationTree.lean#L213

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me