/- Copyright 2026 The Formal Conjectures Authors. Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except in compliance with the License. You may obtain a copy of the License at https://www.apache.org/licenses/LICENSE-2.0 Unless required by applicable law or agreed to in writing, software distributed under the License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the License for the specific language governing permissions and limitations under the License. -/ module public import FormalConjecturesUtil

The burning number conjecture

References:

    [BJR16] Bonato, A., Janssen, J., and Roshanbin, E. (2016). "How to burn a graph." Internet Math. 12, pp. 85--100. arXiv:1507.06524

    [NT24] Norin, S. and Turcotte, J. (2024). "The burning number conjecture holds asymptotically." J. Combin. Theory Ser. B 168, pp. 208--235. arXiv:2207.04035

@[expose] public sectionnamespace BurningNumberConjecturevariable {V : Type*}

The ball-cover condition for burning a graph: every vertex is reachable from some centre x i at distance at most k - 1 - i. The centres may repeat or already be burning when their round starts. For finite graphs, the least such k is the usual burning number [BJR16, Corollary 3].

def IsBurningSequence (G : SimpleGraph V) {k : ℕ} (x : Fin k → V) : Prop := ∀ v, ∃ i, G.Reachable (x i) v ∧ G.dist (x i) v + (i : ℕ) < k

The burning number b(G): the least number of rounds needed to burn every vertex of G.

noncomputable def burningNumber (G : SimpleGraph V) : ℕ := sInf {k | ∃ x : Fin k → V, IsBurningSequence G x}

On a nonempty graph, at least one round is needed.

V:Type u_1inst✝:Nonempty VG:SimpleGraph Vh:∅.Nonemptyh0:burningNumber G = 0h':{k | ∃ x, IsBurningSequence G x} = ∅⊢ False All goals completed! 🐙

The burning number conjecture (Bonato–Janssen–Roshanbin [BJR16]).

Every connected graph on n vertices can be burned in at most ⌈√n⌉ rounds: fires started at one new vertex per round, each spreading to all neighbouring vertices every round, can burn the whole graph in ⌈√n⌉ rounds.

@[category research open, AMS 5] theorem burning_number_conjecture {V : Type} [Fintype V] (G : SimpleGraph V) (hc : G.Connected) : burningNumber G ≤ ⌈Real.sqrt (Fintype.card V)⌉₊ := V:Typeinst✝:Fintype VG:SimpleGraph Vhc:G.Connected⊢ burningNumber G ≤ ⌈√↑(Fintype.card V)⌉₊ All goals completed! 🐙

Paths attain the conjectured bound (Bonato–Janssen–Roshanbin [BJR16]).

The burning number of the path on n ≥ 1 vertices is exactly ⌈√n⌉, so the bound in the burning number conjecture cannot be improved.

@[category research solved, AMS 5] theorem burning_number_conjecture.variants.path (n : ℕ) (hn : 1 ≤ n) : burningNumber (SimpleGraph.pathGraph n) = ⌈Real.sqrt n⌉₊ := n:ℕhn:1 ≤ n⊢ burningNumber (SimpleGraph.pathGraph n) = ⌈√↑n⌉₊ All goals completed! 🐙

Norin–Turcotte (2024): the burning number conjecture holds asymptotically.

For every ε > 0, every sufficiently large connected graph on n vertices can be burned in at most (1 + ε) √n rounds.

Reference: [NT24].

@[category research solved, AMS 5] theorem burning_number_conjecture.variants.norin_turcotte (ε : ℝ) (hε : 0 < ε) : ∃ n₀ : ℕ, ∀ (V : Type) [Fintype V] (G : SimpleGraph V), G.Connected → n₀ ≤ Fintype.card V → (burningNumber G : ℝ) ≤ (1 + ε) * Real.sqrt (Fintype.card V) := ε:ℝhε:0 < ε⊢ ∃ n₀, ∀ (V : Type) [inst : Fintype V] (G : SimpleGraph V), G.Connected → n₀ ≤ Fintype.card V → ↑(burningNumber G) ≤ (1 + ε) * √↑(Fintype.card V) All goals completed! 🐙

A graph with one vertex burns in one round.

V:Type u_1inst✝:Unique VG:SimpleGraph Vh:IsBurningSequence G fun x ↦ default⊢ burningNumber G = 1 All goals completed! 🐙

Complete graphs burn in at most two rounds.

The first fire spreads to every vertex in the second round.

@[category test, AMS 5] theorem burning_number_conjecture.variants.complete [Nonempty V] : burningNumber (⊤ : SimpleGraph V) ≤ 2 := V:Type u_1inst✝:Nonempty V⊢ burningNumber ⊤ ≤ 2 V:Type u_1inst✝:Nonempty Vv:V⊢ ∃ i, ⊤.Reachable ((fun x ↦ Classical.arbitrary V) i) v ∧ ⊤.dist ((fun x ↦ Classical.arbitrary V) i) v + ↑i < 2 V:Type u_1inst✝:Nonempty Vv:Vhv:Classical.arbitrary V = v⊢ ∃ i, ⊤.Reachable ((fun x ↦ Classical.arbitrary V) i) v ∧ ⊤.dist ((fun x ↦ Classical.arbitrary V) i) v + ↑i < 2V:Type u_1inst✝:Nonempty Vv:Vhv:¬Classical.arbitrary V = v⊢ ∃ i, ⊤.Reachable ((fun x ↦ Classical.arbitrary V) i) v ∧ ⊤.dist ((fun x ↦ Classical.arbitrary V) i) v + ↑i < 2 V:Type u_1inst✝:Nonempty Vv:Vhv:Classical.arbitrary V = v⊢ ∃ i, ⊤.Reachable ((fun x ↦ Classical.arbitrary V) i) v ∧ ⊤.dist ((fun x ↦ Classical.arbitrary V) i) v + ↑i < 2 V:Type u_1inst✝:Nonempty V⊢ ∃ i, ⊤.Reachable ((fun x ↦ Classical.arbitrary V) i) (Classical.arbitrary V) ∧ ⊤.dist ((fun x ↦ Classical.arbitrary V) i) (Classical.arbitrary V) + ↑i < 2 exact ⟨0, SimpleGraph.Reachable.refl _, V:Type u_1inst✝:Nonempty V⊢ ⊤.dist ((fun x ↦ Classical.arbitrary V) 0) (Classical.arbitrary V) + ↑0 < 2 All goals completed! 🐙⟩ V:Type u_1inst✝:Nonempty Vv:Vhv:¬Classical.arbitrary V = v⊢ ∃ i, ⊤.Reachable ((fun x ↦ Classical.arbitrary V) i) v ∧ ⊤.dist ((fun x ↦ Classical.arbitrary V) i) v + ↑i < 2 V:Type u_1inst✝:Nonempty Vv:Vhv:¬Classical.arbitrary V = vhadj:⊤.Adj (Classical.arbitrary V) v⊢ ∃ i, ⊤.Reachable ((fun x ↦ Classical.arbitrary V) i) v ∧ ⊤.dist ((fun x ↦ Classical.arbitrary V) i) v + ↑i < 2 V:Type u_1inst✝:Nonempty Vv:Vhv:¬Classical.arbitrary V = vhadj:⊤.Adj (Classical.arbitrary V) vhd:⊤.dist (Classical.arbitrary V) v ≤ (SimpleGraph.Walk.cons hadj SimpleGraph.Walk.nil).length⊢ ∃ i, ⊤.Reachable ((fun x ↦ Classical.arbitrary V) i) v ∧ ⊤.dist ((fun x ↦ Classical.arbitrary V) i) v + ↑i < 2 V:Type u_1inst✝:Nonempty Vv:Vhv:¬Classical.arbitrary V = vhadj:⊤.Adj (Classical.arbitrary V) vhd:⊤.dist (Classical.arbitrary V) v ≤ (SimpleGraph.Walk.cons hadj SimpleGraph.Walk.nil).length⊢ ⊤.dist ((fun x ↦ Classical.arbitrary V) 0) v + ↑0 < 2 V:Type u_1inst✝:Nonempty Vv:Vhv:¬Classical.arbitrary V = vhadj:⊤.Adj (Classical.arbitrary V) vhd:⊤.dist (Classical.arbitrary V) v ≤ 0 + 1⊢ ⊤.dist ((fun x ↦ Classical.arbitrary V) 0) v + ↑0 < 2 All goals completed! 🐙end BurningNumberConjecture