/-
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 FormalConjecturesUtilThe 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.
inr V:Type u_1inst✝:Nonempty VG:SimpleGraph Vh:∅.Nonemptyh0:burningNumber G = 0h':{k | ∃ x, IsBurningSequence G x} = ∅⊢ False
exact Set.not_nonempty_empty h 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)⌉₊ := by V:Typeinst✝:Fintype VG:SimpleGraph Vhc:G.Connected⊢ burningNumber G ≤ ⌈√↑(Fintype.card V)⌉₊
sorry 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⌉₊ := by n:ℕhn:1 ≤ n⊢ burningNumber (SimpleGraph.pathGraph n) = ⌈√↑n⌉₊
sorry 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) := by ε:ℝhε:0 < ε⊢ ∃ n₀,
∀ (V : Type) [inst : Fintype V] (G : SimpleGraph V),
G.Connected → n₀ ≤ Fintype.card V → ↑(burningNumber G) ≤ (1 + ε) * √↑(Fintype.card V)
sorry All goals completed! 🐙A graph with one vertex burns in one round.
@[category test, AMS 5]
theorem burning_number_conjecture.variants.unique [Unique V] (G : SimpleGraph V) :
burningNumber G = 1 := by V:Type u_1inst✝:Unique VG:SimpleGraph V⊢ burningNumber G = 1
have h : IsBurningSequence G (fun _ : Fin 1 => default) := by
intro v V:Type u_1inst✝:Unique VG:SimpleGraph Vv:V⊢ ∃ i, G.Reachable ((fun x ↦ default) i) v ∧ G.dist ((fun x ↦ default) i) v + ↑i < 1 V:Type u_1inst✝:Unique VG:SimpleGraph Vh:IsBurningSequence G fun x ↦ default⊢ burningNumber G = 1
have hv : v = default := Unique.eq_default v V:Type u_1inst✝:Unique VG:SimpleGraph Vv:Vhv:v = default⊢ ∃ i, G.Reachable ((fun x ↦ default) i) v ∧ G.dist ((fun x ↦ default) i) v + ↑i < 1 V:Type u_1inst✝:Unique VG:SimpleGraph Vh:IsBurningSequence G fun x ↦ default⊢ burningNumber G = 1
subst hv V:Type u_1inst✝:Unique VG:SimpleGraph V⊢ ∃ i, G.Reachable ((fun x ↦ default) i) default ∧ G.dist ((fun x ↦ default) i) default + ↑i < 1 V:Type u_1inst✝:Unique VG:SimpleGraph Vh:IsBurningSequence G fun x ↦ default⊢ burningNumber G = 1
exact ⟨0, SimpleGraph.Reachable.refl _, by V:Type u_1inst✝:Unique VG:SimpleGraph V⊢ G.dist ((fun x ↦ default) 0) default + ↑0 < 1 V:Type u_1inst✝:Unique VG:SimpleGraph Vh:IsBurningSequence G fun x ↦ default⊢ burningNumber G = 1 simp All goals completed! 🐙 V:Type u_1inst✝:Unique VG:SimpleGraph Vh:IsBurningSequence G fun x ↦ default⊢ burningNumber G = 1⟩ V:Type u_1inst✝:Unique VG:SimpleGraph Vh:IsBurningSequence G fun x ↦ default⊢ burningNumber G = 1
exact le_antisymm (Nat.sInf_le ⟨_, h⟩) (one_le_burningNumber G ⟨1, _, h⟩) 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 := by V:Type u_1inst✝:Nonempty V⊢ burningNumber ⊤ ≤ 2
refine Nat.sInf_le ⟨fun _ => Classical.arbitrary V, fun v => ?_⟩ 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
by_cases hv : Classical.arbitrary V = v pos 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 < 2neg 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
· pos 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 subst hv pos 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 _, by V:Type u_1inst✝:Nonempty V⊢ ⊤.dist ((fun x ↦ Classical.arbitrary V) 0) (Classical.arbitrary V) + ↑0 < 2 simp All goals completed! 🐙⟩
· neg 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 have hadj : (⊤ : SimpleGraph V).Adj (Classical.arbitrary V) v := hv neg 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
have hd := SimpleGraph.dist_le (SimpleGraph.Walk.cons hadj SimpleGraph.Walk.nil) neg 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
refine ⟨0, ⟨SimpleGraph.Walk.cons hadj SimpleGraph.Walk.nil⟩, ?_⟩ neg 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
simp only [SimpleGraph.Walk.length_cons, SimpleGraph.Walk.length_nil] at hd neg 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
simpa using Nat.lt_succ_of_le hd All goals completed! 🐙end BurningNumberConjecture