VizingConjecture.lean`

Explanation legend Lean4 Domain Explanation Language (L4DEL)

L4DEL explanations are a separate layer. They do not change the Lean source. Intuition is explanatory prose; numbered items are a reading path; sources link the wording back to evidence.

L4DEL: Lean4 Domain Explanation Language

Annotation provenance. This overlay contains 10 curated AI-written annotations and 7190 mechanical source-derived annotations. They have not been human-reviewed as explanations; treat them as unverified and not mathematical authority. Retained generation history: The 71 original curated annotations were produced in a Claude Sonnet 5.5 session at medium effort; Claude Opus 5.5 is recorded in that session as the advisor model, not the direct author. The bulk source-derived expansion was generated mechanically from pinned source comments by tooling developed in a GPT-5.6 Sol session at ultra reasoning; GPT-5.6 Sol did not originate the quoted source prose. On 2026-10-17 the mechanically generated source-comment annotations of the Formal Conjectures, Carleson, FLT, PFR, CompFiles, Mathematics in Lean and Theorem Proving in Lean overlays were regenerated by the same generator after three corrections made in a Claude Sonnet 5.5 session: titles no longer cut a sentence inside mathematics or end on a dangling word, workflow markers are removed from the quoted prose, and declaration names follow the scanner's namespace resolution. The boilerplate step line was dropped, and comments that were only a row of dashes no longer yield annotations. No new prose was written and no human review is claimed.

Credit: The upstream authors and contributors retain credit for the project and mathematics. lean4-explainer only renders their pinned source and adds the separately disclosed explanation layer.

Project sources: Pinned project documentation, Formal Conjectures paper, arXiv v1

4 declarations, 3 contain sorry, 0 declared as axioms

Vizing's conjecture (1968)

References:

Wikipedia
[Vi68] Vizing, V. G. (1968). "Some unsolved problems in graph theory." Uspekhi Mat. Nauk 23, pp. 117--134.
[ClSu00] Clark, W. E. and Suen, S. (2000). "An inequality related to Vizing's conjecture." Electron. J. Combin. 7, N4.
[SuTa12] Suen, S. and Tarr, J. (2012). "An improved inequality related to Vizing's conjecture." Electron. J. Combin. 19, P8.
[BDGHHKR12] Brešar, B., Dorbec, P., Goddard, W., Hartnell, B. L., Henning, M. A., Klavžar, S. and Rall, D. F. (2012). "Vizing's conjecture: a survey and recent results." J. Graph Theory 69, pp. 46--76.

Imports (1)

FormalConjecturesUtil

theorem VizingConjecture.vizing_conjecture Vizing's conjecture (1968) sorry line 49 source
Source documentation
Vizing's conjecture (1968).
For all finite simple graphs $G$ and $H$, the domination number of the Cartesian (box) product satisfies $\gamma(G \,\square\, H) \ge \gamma(G)\,\gamma(H)$.

depends on sorry what this means
Statement uses: Iff, True, Fintype, DecidableEq, SimpleGraph, LE.le, Nat, HMul.hMul, SimpleGraph.dominationNumber, Prod, SimpleGraph.boxProd
Proof uses: sorryAx, Lean.Name, Bool.false, Lean.Name.num, Lean.Name.str, Lean.Name.anonymous, OfNat.ofNat
7 instances, coercions and auxiliary constants left out.

Tactic trace: 1 steps
Open to load the checked before-and-after goal states.
```
theorem vizing_conjecture : answer(sorry) ↔
    ∀ {α β : Type} [Fintype α] [Fintype β] [DecidableEq α] [DecidableEq β]
      (G : SimpleGraph α) (H : SimpleGraph β),
      G.dominationNumber * H.dominationNumber ≤ (G □ H).dominationNumber := by
…
```
theorem VizingConjecture.vizing_conjecture.variants.clark_suen The Clark–Suen inequality (2000) sorry line 65 source
Source documentation
The Clark–Suen inequality (2000).
For all finite simple graphs $G$ and $H$, $\gamma(G \,\square\, H) \ge \tfrac12\,\gamma(G)\,\gamma(H)$; that is, Vizing's conjecture holds up to a factor of $2$.
Reference: [ClSu00].

depends on sorry what this means
Statement uses: Fintype, DecidableEq, SimpleGraph, LE.le, Nat, HMul.hMul, SimpleGraph.dominationNumber, OfNat.ofNat, Prod, SimpleGraph.boxProd
Proof uses: sorryAx, Lean.Name, Bool.false, Lean.Name.num, Lean.Name.str, Lean.Name.anonymous
8 instances, coercions and auxiliary constants left out.

Tactic trace: 1 steps
Open to load the checked before-and-after goal states.
```
theorem vizing_conjecture.variants.clark_suen
    {α β : Type} [Fintype α] [Fintype β] [DecidableEq α] [DecidableEq β]
    (G : SimpleGraph α) (H : SimpleGraph β) :
    G.dominationNumber * H.dominationNumber ≤ 2 * (G □ H).dominationNumber := by
…
```
theorem VizingConjecture.vizing_conjecture.variants.suen_tarr The Suen–Tarr inequality (2012) sorry line 81 source
Source documentation
The Suen–Tarr inequality (2012).
For all finite simple graphs $G$ and $H$, $\gamma(G \,\square\, H) \ge \tfrac12\,\gamma(G)\,\gamma(H) + \tfrac12\min\{\gamma(G), \gamma(H)\}$, improving the Clark–Suen bound.
Reference: [SuTa12].

depends on sorry what this means
Statement uses: Fintype, DecidableEq, SimpleGraph, LE.le, Nat, HAdd.hAdd, HMul.hMul, SimpleGraph.dominationNumber, Min.min, OfNat.ofNat, Prod, SimpleGraph.boxProd
Proof uses: sorryAx, Lean.Name, Bool.false, Lean.Name.num, Lean.Name.str, Lean.Name.anonymous
14 instances, coercions and auxiliary constants left out.

Tactic trace: 1 steps
Open to load the checked before-and-after goal states.
```
theorem vizing_conjecture.variants.suen_tarr
    {α β : Type} [Fintype α] [Fintype β] [DecidableEq α] [DecidableEq β]
    (G : SimpleGraph α) (H : SimpleGraph β) :
    G.dominationNumber * H.dominationNumber + min G.dominationNumber H.dominationNumber ≤
      2 * (G □ H).dominationNumber := by
…
```
theorem VizingConjecture.vizing_conjecture.variants.dominationNumber_eq_one Vizing's conjecture when γ(H) = 1 line 97 source
Source documentation
Vizing's conjecture when γ(H) = 1.
If H has a dominating vertex, so that $\gamma(H) = 1$, then Vizing's inequality reduces to $\gamma(G) \le \gamma(G \,\square\, H)$, which is the projection bound dominationNumber_le_dominationNumber_boxProd. This is the simplest of the known cases of the conjecture (see [BDGHHKR12]).

standard axioms: Classical.choice, Quot.sound, propext what this means
Statement uses: Fintype, DecidableEq, SimpleGraph, Eq, Nat, SimpleGraph.dominationNumber, OfNat.ofNat, LE.le, HMul.hMul, Prod, SimpleGraph.boxProd
Proof uses: Nonempty, Classical.byContradiction, Not, Iff.mp, Nat.le_zero, SimpleGraph.dominationNumber_le_of_isDominating, EmptyCollection.emptyCollection, Finset, False.elim, Or, Membership.mem, Set, Exists, And, SimpleGraph.Adj, IsEmpty.false, Eq.mp, IsEmpty, congrArg, propext and 5 more
18 instances, coercions and auxiliary constants left out.

Tactic trace: 7 steps
Open to load the checked before-and-after goal states.
```
theorem vizing_conjecture.variants.dominationNumber_eq_one
    {α β : Type} [Fintype α] [Fintype β] [DecidableEq α] [DecidableEq β]
    (G : SimpleGraph α) (H : SimpleGraph β) (hH : H.dominationNumber = 1) :
    G.dominationNumber * H.dominationNumber ≤ (G □ H).dominationNumber := by
…
```