/-
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 Mathlib.Analysis.RCLike.Basic
public import Mathlib.Combinatorics.SimpleGraph.Connectivity.Finite
public import Mathlib.Combinatorics.SimpleGraph.Metric
public import Mathlib.Tactic.IntervalCases
public import FormalConjecturesForMathlib.Combinatorics.SimpleGraph.Connectivity@[expose] public sectionnamespace SimpleGraphvariable {α : Type*} [Fintype α] [DecidableEq α]Distance from a vertex to a finite set.
noncomputable def distToSet (G : SimpleGraph α) (v : α) (S : Set α) : ℕ :=
open scoped Classical in
if h : S.toFinset.Nonempty then
(S.toFinset.image (fun s => G.dist v s)).min' (Finset.Nonempty.image h _)
else 0
Average distance of G.
noncomputable def averageDistance (G : SimpleGraph α) : ℝ :=
if Fintype.card α > 1 then
(∑ u ∈ Finset.univ, ∑ v ∈ Finset.univ, (G.dist u v : ℝ)) /
((Fintype.card α : ℝ) * ((Fintype.card α : ℝ) - 1))
else
0
Check if a list of vertices forms an induced path in G.
def isInducedPath (G : SimpleGraph α) (l : List α) : Prop :=
l.Nodup ∧ ∀ i j : Fin l.length, G.Adj (l.get i) (l.get j) ↔ i.val + 1 = j.val ∨ j.val + 1 = i.valThe path number of a graph: The number of vertices of a largest induced path of the graph.
noncomputable def path (G : SimpleGraph α) : ℕ :=
open scoped Classical in
let induced_paths := Finset.univ.filter (fun s : Finset α =>
∃ l : List α, l.toFinset = s ∧ isInducedPath G l)
(induced_paths.image Finset.card).max.getD 0
An explicit induced path witnesses a lower bound for path.
coe α:Type u_1inst✝¹:Fintype αinst✝:DecidableEq αG:SimpleGraph αl:List αhl:G.isInducedPath linducedPaths:Finset (Finset α) := {s | ∃ vertices, vertices.toFinset = s ∧ G.isInducedPath vertices}hmem:l.toFinset ∈ inducedPathshcard:l.toFinset.card ∈ Finset.image Finset.card inducedPathsmaximum:ℕhle:↑l.toFinset.card ≤ ↑maximumhmaximum:(Finset.image Finset.card inducedPaths).max = ↑maximum⊢ l.toFinset.card ≤ Option.getD (↑maximum) 0
have hleNat : l.toFinset.card ≤ maximum := WithBot.coe_le_coe.mp hle coe α:Type u_1inst✝¹:Fintype αinst✝:DecidableEq αG:SimpleGraph αl:List αhl:G.isInducedPath linducedPaths:Finset (Finset α) := {s | ∃ vertices, vertices.toFinset = s ∧ G.isInducedPath vertices}hmem:l.toFinset ∈ inducedPathshcard:l.toFinset.card ∈ Finset.image Finset.card inducedPathsmaximum:ℕhle:↑l.toFinset.card ≤ ↑maximumhmaximum:(Finset.image Finset.card inducedPaths).max = ↑maximumhleNat:l.toFinset.card ≤ maximum⊢ l.toFinset.card ≤ Option.getD (↑maximum) 0
simpa [hmaximum, Option.getD] using hleNat All goals completed! 🐙
A uniform upper bound on the lengths of induced paths bounds path.
theorem path_le_of_isInducedPath_length_le (G : SimpleGraph α) (k : ℕ)
(h : ∀ l : List α, G.isInducedPath l → l.length ≤ k) : path G ≤ k := by α:Type u_1inst✝¹:Fintype αinst✝:DecidableEq αG:SimpleGraph αk:ℕh:∀ (l : List α), G.isInducedPath l → l.length ≤ k⊢ G.path ≤ k
classical
unfold path α:Type u_1inst✝¹:Fintype αinst✝:DecidableEq αG:SimpleGraph αk:ℕh:∀ (l : List α), G.isInducedPath l → l.length ≤ k⊢ (have induced_paths := {s | ∃ l, l.toFinset = s ∧ G.isInducedPath l};
Option.getD (Finset.image Finset.card induced_paths).max 0) ≤
k
let inducedPaths := Finset.univ.filter (fun s : Finset α ↦
∃ vertices : List α, vertices.toFinset = s ∧ G.isInducedPath vertices) α:Type u_1inst✝¹:Fintype αinst✝:DecidableEq αG:SimpleGraph αk:ℕh:∀ (l : List α), G.isInducedPath l → l.length ≤ kinducedPaths:Finset (Finset α) := {s | ∃ vertices, vertices.toFinset = s ∧ G.isInducedPath vertices}⊢ (have induced_paths := {s | ∃ l, l.toFinset = s ∧ G.isInducedPath l};
Option.getD (Finset.image Finset.card induced_paths).max 0) ≤
k
change (inducedPaths.image Finset.card).max.getD 0 ≤ k α:Type u_1inst✝¹:Fintype αinst✝:DecidableEq αG:SimpleGraph αk:ℕh:∀ (l : List α), G.isInducedPath l → l.length ≤ kinducedPaths:Finset (Finset α) := {s | ∃ vertices, vertices.toFinset = s ∧ G.isInducedPath vertices}⊢ Option.getD (Finset.image Finset.card inducedPaths).max 0 ≤ k
have hmax : (inducedPaths.image Finset.card).max ≤ (k : WithBot ℕ) := by α:Type u_1inst✝¹:Fintype αinst✝:DecidableEq αG:SimpleGraph αk:ℕh:∀ (l : List α), G.isInducedPath l → l.length ≤ k⊢ G.path ≤ k α:Type u_1inst✝¹:Fintype αinst✝:DecidableEq αG:SimpleGraph αk:ℕh:∀ (l : List α), G.isInducedPath l → l.length ≤ kinducedPaths:Finset (Finset α) := {s | ∃ vertices, vertices.toFinset = s ∧ G.isInducedPath vertices}hmax:(Finset.image Finset.card inducedPaths).max ≤ ↑k⊢ Option.getD (Finset.image Finset.card inducedPaths).max 0 ≤ k
apply Finset.max_le α:Type u_1inst✝¹:Fintype αinst✝:DecidableEq αG:SimpleGraph αk:ℕh:∀ (l : List α), G.isInducedPath l → l.length ≤ kinducedPaths:Finset (Finset α) := {s | ∃ vertices, vertices.toFinset = s ∧ G.isInducedPath vertices}⊢ ∀ a ∈ Finset.image Finset.card inducedPaths, ↑a ≤ ↑k α:Type u_1inst✝¹:Fintype αinst✝:DecidableEq αG:SimpleGraph αk:ℕh:∀ (l : List α), G.isInducedPath l → l.length ≤ kinducedPaths:Finset (Finset α) := {s | ∃ vertices, vertices.toFinset = s ∧ G.isInducedPath vertices}hmax:(Finset.image Finset.card inducedPaths).max ≤ ↑k⊢ Option.getD (Finset.image Finset.card inducedPaths).max 0 ≤ k
intro cardinality hcardinality α:Type u_1inst✝¹:Fintype αinst✝:DecidableEq αG:SimpleGraph αk:ℕh:∀ (l : List α), G.isInducedPath l → l.length ≤ kinducedPaths:Finset (Finset α) := {s | ∃ vertices, vertices.toFinset = s ∧ G.isInducedPath vertices}cardinality:ℕhcardinality:cardinality ∈ Finset.image Finset.card inducedPaths⊢ ↑cardinality ≤ ↑k α:Type u_1inst✝¹:Fintype αinst✝:DecidableEq αG:SimpleGraph αk:ℕh:∀ (l : List α), G.isInducedPath l → l.length ≤ kinducedPaths:Finset (Finset α) := {s | ∃ vertices, vertices.toFinset = s ∧ G.isInducedPath vertices}hmax:(Finset.image Finset.card inducedPaths).max ≤ ↑k⊢ Option.getD (Finset.image Finset.card inducedPaths).max 0 ≤ k
obtain ⟨s, hs, rfl⟩ := Finset.mem_image.mp hcardinality α:Type u_1inst✝¹:Fintype αinst✝:DecidableEq αG:SimpleGraph αk:ℕh:∀ (l : List α), G.isInducedPath l → l.length ≤ kinducedPaths:Finset (Finset α) := {s | ∃ vertices, vertices.toFinset = s ∧ G.isInducedPath vertices}s:Finset αhs:s ∈ inducedPathshcardinality:s.card ∈ Finset.image Finset.card inducedPaths⊢ ↑s.card ≤ ↑k α:Type u_1inst✝¹:Fintype αinst✝:DecidableEq αG:SimpleGraph αk:ℕh:∀ (l : List α), G.isInducedPath l → l.length ≤ kinducedPaths:Finset (Finset α) := {s | ∃ vertices, vertices.toFinset = s ∧ G.isInducedPath vertices}hmax:(Finset.image Finset.card inducedPaths).max ≤ ↑k⊢ Option.getD (Finset.image Finset.card inducedPaths).max 0 ≤ k
obtain ⟨_, vertices, rfl, hvertices⟩ := Finset.mem_filter.mp hs α:Type u_1inst✝¹:Fintype αinst✝:DecidableEq αG:SimpleGraph αk:ℕh:∀ (l : List α), G.isInducedPath l → l.length ≤ kinducedPaths:Finset (Finset α) := {s | ∃ vertices, vertices.toFinset = s ∧ G.isInducedPath vertices}vertices:List αhvertices:G.isInducedPath verticeshs:vertices.toFinset ∈ inducedPathshcardinality:vertices.toFinset.card ∈ Finset.image Finset.card inducedPathsleft✝:vertices.toFinset ∈ Finset.univ⊢ ↑vertices.toFinset.card ≤ ↑k α:Type u_1inst✝¹:Fintype αinst✝:DecidableEq αG:SimpleGraph αk:ℕh:∀ (l : List α), G.isInducedPath l → l.length ≤ kinducedPaths:Finset (Finset α) := {s | ∃ vertices, vertices.toFinset = s ∧ G.isInducedPath vertices}hmax:(Finset.image Finset.card inducedPaths).max ≤ ↑k⊢ Option.getD (Finset.image Finset.card inducedPaths).max 0 ≤ k
rw [List.toFinset_card_of_nodup hvertices.1 α:Type u_1inst✝¹:Fintype αinst✝:DecidableEq αG:SimpleGraph αk:ℕh:∀ (l : List α), G.isInducedPath l → l.length ≤ kinducedPaths:Finset (Finset α) := {s | ∃ vertices, vertices.toFinset = s ∧ G.isInducedPath vertices}vertices:List αhvertices:G.isInducedPath verticeshs:vertices.toFinset ∈ inducedPathshcardinality:vertices.toFinset.card ∈ Finset.image Finset.card inducedPathsleft✝:vertices.toFinset ∈ Finset.univ⊢ ↑vertices.length ≤ ↑k α:Type u_1inst✝¹:Fintype αinst✝:DecidableEq αG:SimpleGraph αk:ℕh:∀ (l : List α), G.isInducedPath l → l.length ≤ kinducedPaths:Finset (Finset α) := {s | ∃ vertices, vertices.toFinset = s ∧ G.isInducedPath vertices}vertices:List αhvertices:G.isInducedPath verticeshs:vertices.toFinset ∈ inducedPathshcardinality:vertices.toFinset.card ∈ Finset.image Finset.card inducedPathsleft✝:vertices.toFinset ∈ Finset.univ⊢ ↑vertices.length ≤ ↑k α:Type u_1inst✝¹:Fintype αinst✝:DecidableEq αG:SimpleGraph αk:ℕh:∀ (l : List α), G.isInducedPath l → l.length ≤ kinducedPaths:Finset (Finset α) := {s | ∃ vertices, vertices.toFinset = s ∧ G.isInducedPath vertices}hmax:(Finset.image Finset.card inducedPaths).max ≤ ↑k⊢ Option.getD (Finset.image Finset.card inducedPaths).max 0 ≤ k] α:Type u_1inst✝¹:Fintype αinst✝:DecidableEq αG:SimpleGraph αk:ℕh:∀ (l : List α), G.isInducedPath l → l.length ≤ kinducedPaths:Finset (Finset α) := {s | ∃ vertices, vertices.toFinset = s ∧ G.isInducedPath vertices}vertices:List αhvertices:G.isInducedPath verticeshs:vertices.toFinset ∈ inducedPathshcardinality:vertices.toFinset.card ∈ Finset.image Finset.card inducedPathsleft✝:vertices.toFinset ∈ Finset.univ⊢ ↑vertices.length ≤ ↑k α:Type u_1inst✝¹:Fintype αinst✝:DecidableEq αG:SimpleGraph αk:ℕh:∀ (l : List α), G.isInducedPath l → l.length ≤ kinducedPaths:Finset (Finset α) := {s | ∃ vertices, vertices.toFinset = s ∧ G.isInducedPath vertices}hmax:(Finset.image Finset.card inducedPaths).max ≤ ↑k⊢ Option.getD (Finset.image Finset.card inducedPaths).max 0 ≤ k
exact WithBot.coe_le_coe.mpr (h vertices hvertices) α:Type u_1inst✝¹:Fintype αinst✝:DecidableEq αG:SimpleGraph αk:ℕh:∀ (l : List α), G.isInducedPath l → l.length ≤ kinducedPaths:Finset (Finset α) := {s | ∃ vertices, vertices.toFinset = s ∧ G.isInducedPath vertices}hmax:(Finset.image Finset.card inducedPaths).max ≤ ↑k⊢ Option.getD (Finset.image Finset.card inducedPaths).max 0 ≤ k α:Type u_1inst✝¹:Fintype αinst✝:DecidableEq αG:SimpleGraph αk:ℕh:∀ (l : List α), G.isInducedPath l → l.length ≤ kinducedPaths:Finset (Finset α) := {s | ∃ vertices, vertices.toFinset = s ∧ G.isInducedPath vertices}hmax:(Finset.image Finset.card inducedPaths).max ≤ ↑k⊢ Option.getD (Finset.image Finset.card inducedPaths).max 0 ≤ k
cases hmaximum : (inducedPaths.image Finset.card).max with
| bot => bot α:Type u_1inst✝¹:Fintype αinst✝:DecidableEq αG:SimpleGraph αk:ℕh:∀ (l : List α), G.isInducedPath l → l.length ≤ kinducedPaths:Finset (Finset α) := {s | ∃ vertices, vertices.toFinset = s ∧ G.isInducedPath vertices}hmax:(Finset.image Finset.card inducedPaths).max ≤ ↑khmaximum:(Finset.image Finset.card inducedPaths).max = ⊥⊢ Option.getD ⊥ 0 ≤ k exact Nat.zero_le k All goals completed! 🐙
| coe maximum => coe α:Type u_1inst✝¹:Fintype αinst✝:DecidableEq αG:SimpleGraph αk:ℕh:∀ (l : List α), G.isInducedPath l → l.length ≤ kinducedPaths:Finset (Finset α) := {s | ∃ vertices, vertices.toFinset = s ∧ G.isInducedPath vertices}hmax:(Finset.image Finset.card inducedPaths).max ≤ ↑kmaximum:ℕhmaximum:(Finset.image Finset.card inducedPaths).max = ↑maximum⊢ Option.getD (↑maximum) 0 ≤ k
have : maximum ≤ k := by α:Type u_1inst✝¹:Fintype αinst✝:DecidableEq αG:SimpleGraph αk:ℕh:∀ (l : List α), G.isInducedPath l → l.length ≤ k⊢ G.path ≤ k coe α:Type u_1inst✝¹:Fintype αinst✝:DecidableEq αG:SimpleGraph αk:ℕh:∀ (l : List α), G.isInducedPath l → l.length ≤ kinducedPaths:Finset (Finset α) := {s | ∃ vertices, vertices.toFinset = s ∧ G.isInducedPath vertices}hmax:(Finset.image Finset.card inducedPaths).max ≤ ↑kmaximum:ℕhmaximum:(Finset.image Finset.card inducedPaths).max = ↑maximumthis:maximum ≤ k⊢ Option.getD (↑maximum) 0 ≤ k
rw [hmaximum α:Type u_1inst✝¹:Fintype αinst✝:DecidableEq αG:SimpleGraph αk:ℕh:∀ (l : List α), G.isInducedPath l → l.length ≤ kinducedPaths:Finset (Finset α) := {s | ∃ vertices, vertices.toFinset = s ∧ G.isInducedPath vertices}maximum:ℕhmax:↑maximum ≤ ↑khmaximum:(Finset.image Finset.card inducedPaths).max = ↑maximum⊢ maximum ≤ k α:Type u_1inst✝¹:Fintype αinst✝:DecidableEq αG:SimpleGraph αk:ℕh:∀ (l : List α), G.isInducedPath l → l.length ≤ kinducedPaths:Finset (Finset α) := {s | ∃ vertices, vertices.toFinset = s ∧ G.isInducedPath vertices}maximum:ℕhmax:↑maximum ≤ ↑khmaximum:(Finset.image Finset.card inducedPaths).max = ↑maximum⊢ maximum ≤ kcoe α:Type u_1inst✝¹:Fintype αinst✝:DecidableEq αG:SimpleGraph αk:ℕh:∀ (l : List α), G.isInducedPath l → l.length ≤ kinducedPaths:Finset (Finset α) := {s | ∃ vertices, vertices.toFinset = s ∧ G.isInducedPath vertices}hmax:(Finset.image Finset.card inducedPaths).max ≤ ↑kmaximum:ℕhmaximum:(Finset.image Finset.card inducedPaths).max = ↑maximumthis:maximum ≤ k⊢ Option.getD (↑maximum) 0 ≤ k] at hmax α:Type u_1inst✝¹:Fintype αinst✝:DecidableEq αG:SimpleGraph αk:ℕh:∀ (l : List α), G.isInducedPath l → l.length ≤ kinducedPaths:Finset (Finset α) := {s | ∃ vertices, vertices.toFinset = s ∧ G.isInducedPath vertices}maximum:ℕhmax:↑maximum ≤ ↑khmaximum:(Finset.image Finset.card inducedPaths).max = ↑maximum⊢ maximum ≤ kcoe α:Type u_1inst✝¹:Fintype αinst✝:DecidableEq αG:SimpleGraph αk:ℕh:∀ (l : List α), G.isInducedPath l → l.length ≤ kinducedPaths:Finset (Finset α) := {s | ∃ vertices, vertices.toFinset = s ∧ G.isInducedPath vertices}hmax:(Finset.image Finset.card inducedPaths).max ≤ ↑kmaximum:ℕhmaximum:(Finset.image Finset.card inducedPaths).max = ↑maximumthis:maximum ≤ k⊢ Option.getD (↑maximum) 0 ≤ k
exact WithBot.coe_le_coe.mp hmaxcoe α:Type u_1inst✝¹:Fintype αinst✝:DecidableEq αG:SimpleGraph αk:ℕh:∀ (l : List α), G.isInducedPath l → l.length ≤ kinducedPaths:Finset (Finset α) := {s | ∃ vertices, vertices.toFinset = s ∧ G.isInducedPath vertices}hmax:(Finset.image Finset.card inducedPaths).max ≤ ↑kmaximum:ℕhmaximum:(Finset.image Finset.card inducedPaths).max = ↑maximumthis:maximum ≤ k⊢ Option.getD (↑maximum) 0 ≤ kcoe α:Type u_1inst✝¹:Fintype αinst✝:DecidableEq αG:SimpleGraph αk:ℕh:∀ (l : List α), G.isInducedPath l → l.length ≤ kinducedPaths:Finset (Finset α) := {s | ∃ vertices, vertices.toFinset = s ∧ G.isInducedPath vertices}hmax:(Finset.image Finset.card inducedPaths).max ≤ ↑kmaximum:ℕhmaximum:(Finset.image Finset.card inducedPaths).max = ↑maximumthis:maximum ≤ k⊢ Option.getD (↑maximum) 0 ≤ k
simpa [hmaximum, Option.getD] using this All goals completed! 🐙
If G has no induced path on k + 1 vertices, then path G ≤ k.
theorem path_le_of_not_exists_inducedPath_succ (G : SimpleGraph α) (k : ℕ)
(h : ¬ ∃ e : Fin (k + 1) → α, Function.Injective e ∧
∀ i j : Fin (k + 1), G.Adj (e i) (e j) ↔
i.val + 1 = j.val ∨ j.val + 1 = i.val) : path G ≤ k := by α:Type u_1inst✝¹:Fintype αinst✝:DecidableEq αG:SimpleGraph αk:ℕh:¬∃ e, Function.Injective e ∧ ∀ (i j : Fin (k + 1)), G.Adj (e i) (e j) ↔ ↑i + 1 = ↑j ∨ ↑j + 1 = ↑i⊢ G.path ≤ k
classical
apply path_le_of_isInducedPath_length_le G k α:Type u_1inst✝¹:Fintype αinst✝:DecidableEq αG:SimpleGraph αk:ℕh:¬∃ e, Function.Injective e ∧ ∀ (i j : Fin (k + 1)), G.Adj (e i) (e j) ↔ ↑i + 1 = ↑j ∨ ↑j + 1 = ↑i⊢ ∀ (l : List α), G.isInducedPath l → l.length ≤ k
intro l hl α:Type u_1inst✝¹:Fintype αinst✝:DecidableEq αG:SimpleGraph αk:ℕh:¬∃ e, Function.Injective e ∧ ∀ (i j : Fin (k + 1)), G.Adj (e i) (e j) ↔ ↑i + 1 = ↑j ∨ ↑j + 1 = ↑il:List αhl:G.isInducedPath l⊢ l.length ≤ k
by_contra hlength α:Type u_1inst✝¹:Fintype αinst✝:DecidableEq αG:SimpleGraph αk:ℕh:¬∃ e, Function.Injective e ∧ ∀ (i j : Fin (k + 1)), G.Adj (e i) (e j) ↔ ↑i + 1 = ↑j ∨ ↑j + 1 = ↑il:List αhl:G.isInducedPath lhlength:¬l.length ≤ k⊢ False
have hprefix : k + 1 ≤ l.length := by α:Type u_1inst✝¹:Fintype αinst✝:DecidableEq αG:SimpleGraph αk:ℕh:¬∃ e, Function.Injective e ∧ ∀ (i j : Fin (k + 1)), G.Adj (e i) (e j) ↔ ↑i + 1 = ↑j ∨ ↑j + 1 = ↑i⊢ G.path ≤ k α:Type u_1inst✝¹:Fintype αinst✝:DecidableEq αG:SimpleGraph αk:ℕh:¬∃ e, Function.Injective e ∧ ∀ (i j : Fin (k + 1)), G.Adj (e i) (e j) ↔ ↑i + 1 = ↑j ∨ ↑j + 1 = ↑il:List αhl:G.isInducedPath lhlength:¬l.length ≤ khprefix:k + 1 ≤ l.length⊢ False omega α:Type u_1inst✝¹:Fintype αinst✝:DecidableEq αG:SimpleGraph αk:ℕh:¬∃ e, Function.Injective e ∧ ∀ (i j : Fin (k + 1)), G.Adj (e i) (e j) ↔ ↑i + 1 = ↑j ∨ ↑j + 1 = ↑il:List αhl:G.isInducedPath lhlength:¬l.length ≤ khprefix:k + 1 ≤ l.length⊢ False α:Type u_1inst✝¹:Fintype αinst✝:DecidableEq αG:SimpleGraph αk:ℕh:¬∃ e, Function.Injective e ∧ ∀ (i j : Fin (k + 1)), G.Adj (e i) (e j) ↔ ↑i + 1 = ↑j ∨ ↑j + 1 = ↑il:List αhl:G.isInducedPath lhlength:¬l.length ≤ khprefix:k + 1 ≤ l.length⊢ False
apply h α:Type u_1inst✝¹:Fintype αinst✝:DecidableEq αG:SimpleGraph αk:ℕh:¬∃ e, Function.Injective e ∧ ∀ (i j : Fin (k + 1)), G.Adj (e i) (e j) ↔ ↑i + 1 = ↑j ∨ ↑j + 1 = ↑il:List αhl:G.isInducedPath lhlength:¬l.length ≤ khprefix:k + 1 ≤ l.length⊢ ∃ e, Function.Injective e ∧ ∀ (i j : Fin (k + 1)), G.Adj (e i) (e j) ↔ ↑i + 1 = ↑j ∨ ↑j + 1 = ↑i
let e : Fin (k + 1) → α := fun i ↦ l.get ⟨i.val, lt_of_lt_of_le i.isLt hprefix⟩ α:Type u_1inst✝¹:Fintype αinst✝:DecidableEq αG:SimpleGraph αk:ℕh:¬∃ e, Function.Injective e ∧ ∀ (i j : Fin (k + 1)), G.Adj (e i) (e j) ↔ ↑i + 1 = ↑j ∨ ↑j + 1 = ↑il:List αhl:G.isInducedPath lhlength:¬l.length ≤ khprefix:k + 1 ≤ l.lengthe:Fin (k + 1) → α := fun i ↦ l.get ⟨↑i, ⋯⟩⊢ ∃ e, Function.Injective e ∧ ∀ (i j : Fin (k + 1)), G.Adj (e i) (e j) ↔ ↑i + 1 = ↑j ∨ ↑j + 1 = ↑i
refine ⟨e, ?_, ?_⟩ refine_1 α:Type u_1inst✝¹:Fintype αinst✝:DecidableEq αG:SimpleGraph αk:ℕh:¬∃ e, Function.Injective e ∧ ∀ (i j : Fin (k + 1)), G.Adj (e i) (e j) ↔ ↑i + 1 = ↑j ∨ ↑j + 1 = ↑il:List αhl:G.isInducedPath lhlength:¬l.length ≤ khprefix:k + 1 ≤ l.lengthe:Fin (k + 1) → α := fun i ↦ l.get ⟨↑i, ⋯⟩⊢ Function.Injective erefine_2 α:Type u_1inst✝¹:Fintype αinst✝:DecidableEq αG:SimpleGraph αk:ℕh:¬∃ e, Function.Injective e ∧ ∀ (i j : Fin (k + 1)), G.Adj (e i) (e j) ↔ ↑i + 1 = ↑j ∨ ↑j + 1 = ↑il:List αhl:G.isInducedPath lhlength:¬l.length ≤ khprefix:k + 1 ≤ l.lengthe:Fin (k + 1) → α := fun i ↦ l.get ⟨↑i, ⋯⟩⊢ ∀ (i j : Fin (k + 1)), G.Adj (e i) (e j) ↔ ↑i + 1 = ↑j ∨ ↑j + 1 = ↑i
· refine_1 α:Type u_1inst✝¹:Fintype αinst✝:DecidableEq αG:SimpleGraph αk:ℕh:¬∃ e, Function.Injective e ∧ ∀ (i j : Fin (k + 1)), G.Adj (e i) (e j) ↔ ↑i + 1 = ↑j ∨ ↑j + 1 = ↑il:List αhl:G.isInducedPath lhlength:¬l.length ≤ khprefix:k + 1 ≤ l.lengthe:Fin (k + 1) → α := fun i ↦ l.get ⟨↑i, ⋯⟩⊢ Function.Injective e intro i j hij refine_1 α:Type u_1inst✝¹:Fintype αinst✝:DecidableEq αG:SimpleGraph αk:ℕh:¬∃ e, Function.Injective e ∧ ∀ (i j : Fin (k + 1)), G.Adj (e i) (e j) ↔ ↑i + 1 = ↑j ∨ ↑j + 1 = ↑il:List αhl:G.isInducedPath lhlength:¬l.length ≤ khprefix:k + 1 ≤ l.lengthe:Fin (k + 1) → α := fun i ↦ l.get ⟨↑i, ⋯⟩i:Fin (k + 1)j:Fin (k + 1)hij:e i = e j⊢ i = j
apply Fin.ext refine_1 α:Type u_1inst✝¹:Fintype αinst✝:DecidableEq αG:SimpleGraph αk:ℕh:¬∃ e, Function.Injective e ∧ ∀ (i j : Fin (k + 1)), G.Adj (e i) (e j) ↔ ↑i + 1 = ↑j ∨ ↑j + 1 = ↑il:List αhl:G.isInducedPath lhlength:¬l.length ≤ khprefix:k + 1 ≤ l.lengthe:Fin (k + 1) → α := fun i ↦ l.get ⟨↑i, ⋯⟩i:Fin (k + 1)j:Fin (k + 1)hij:e i = e j⊢ ↑i = ↑j
exact congrArg (fun n : Fin l.length ↦ n.val) (hl.1.injective_get hij) All goals completed! 🐙
· refine_2 α:Type u_1inst✝¹:Fintype αinst✝:DecidableEq αG:SimpleGraph αk:ℕh:¬∃ e, Function.Injective e ∧ ∀ (i j : Fin (k + 1)), G.Adj (e i) (e j) ↔ ↑i + 1 = ↑j ∨ ↑j + 1 = ↑il:List αhl:G.isInducedPath lhlength:¬l.length ≤ khprefix:k + 1 ≤ l.lengthe:Fin (k + 1) → α := fun i ↦ l.get ⟨↑i, ⋯⟩⊢ ∀ (i j : Fin (k + 1)), G.Adj (e i) (e j) ↔ ↑i + 1 = ↑j ∨ ↑j + 1 = ↑i intro i j refine_2 α:Type u_1inst✝¹:Fintype αinst✝:DecidableEq αG:SimpleGraph αk:ℕh:¬∃ e, Function.Injective e ∧ ∀ (i j : Fin (k + 1)), G.Adj (e i) (e j) ↔ ↑i + 1 = ↑j ∨ ↑j + 1 = ↑il:List αhl:G.isInducedPath lhlength:¬l.length ≤ khprefix:k + 1 ≤ l.lengthe:Fin (k + 1) → α := fun i ↦ l.get ⟨↑i, ⋯⟩i:Fin (k + 1)j:Fin (k + 1)⊢ G.Adj (e i) (e j) ↔ ↑i + 1 = ↑j ∨ ↑j + 1 = ↑i
simpa only [e] using
hl.2 ⟨i.val, lt_of_lt_of_le i.isLt hprefix⟩ ⟨j.val, lt_of_lt_of_le j.isLt hprefix⟩ All goals completed! 🐙
Auxiliary quantity ecc used in conjecture 34.
noncomputable def ecc (G : SimpleGraph α) (S : Set α) : ℕ :=
open scoped Classical in
let s_comp := Finset.univ.filter (fun v => v ∉ S)
if h : s_comp.Nonempty then
(s_comp.image (fun v => distToSet G v S)).max' (Finset.Nonempty.image h _)
else 0
The minimum distance between distinct vertices of $S$:
$\min {\operatorname{dist}_G(u, v) \mid u, v \in S, u \ne v}$. Returns 0 when $S$
contains fewer than two vertices.
noncomputable def distMin (G : SimpleGraph α) (S : Set α) : ℕ :=
open scoped Classical in
let pairs := (S.toFinset ×ˢ S.toFinset).filter (fun p => p.1 ≠ p.2)
if h : pairs.Nonempty then
(pairs.image (fun p => G.dist p.1 p.2)).min' (Finset.Nonempty.image h _)
else 0
The eccentricity of a set S: the maximum, over all vertices v of G, of the
minimum distance from v to any vertex in S. (This includes vertices in S itself,
which contribute distance 0.) Returns 0 when S is empty.
Unlike ecc, which restricts the outer maximum to vertices v ∉ S, eccSet does
not exclude any vertex; it is the conventional definition of "set eccentricity"
used in DeLaVina's WOWII conjectures 142, 145 and 146.
noncomputable def eccSet (G : SimpleGraph α) (S : Set α) : ℕ :=
let dists := Finset.univ.image (fun v => distToSet G v S)
if h : dists.Nonempty then dists.max' h else 0
The maximum distance between two vertices of a set S:
$\operatorname{dist}_{\max}(S) = \max{\operatorname{dist}_G(u,v) \mid u, v \in S}$.
Returns 0 when S is empty or a singleton.
This is DeLaVina's dist_max(S) invariant ("distance between maximum degree
vertices" when S = M), used in WOWII conjecture 18. It is distinct from
eccSet, which measures distances from arbitrary vertices to the set.
noncomputable def distMaxSet (G : SimpleGraph α) (S : Set α) : ℕ :=
open scoped Classical in
let members := Finset.univ.filter (fun v : α => v ∈ S)
(members ×ˢ members).sup (fun p => G.dist p.1 p.2)
The average distance between distinct vertices of a set S:
$\operatorname{dist}_{\operatorname{avg}}(S)$ is the mean of $\operatorname{dist}_G(u, v)$ over
all ordered pairs $(u, v)$ of distinct vertices of $S$. Returns 0 when $S$ contains fewer than
two vertices.
This is DeLaVina's dist_avg(S) invariant ("average distance between maximum degree
vertices" when S = M), used in WOWII conjecture 23. It is distinct from distavg,
which averages the distances from all vertices of G to the set.
noncomputable def distAvgSet (G : SimpleGraph α) (S : Set α) : ℝ :=
open scoped Classical in
let pairs := (S.toFinset ×ˢ S.toFinset).filter (fun p => p.1 ≠ p.2)
if pairs.Nonempty then
(∑ p ∈ pairs, (G.dist p.1 p.2 : ℝ)) / (pairs.card : ℝ)
else 0Average distance from all vertices to a given set.
noncomputable def distavg (G : SimpleGraph α) (S : Set α) : ℝ :=
if Fintype.card α > 0 then
(∑ v ∈ Finset.univ, (distToSet G v S : ℝ)) / (Fintype.card α : ℝ)
else
0
The square of a graph G, denoted G²: two distinct vertices are adjacent
iff their distance in G is at most 2.
The bound uses the extended distance SimpleGraph.edist, which is ⊤ for unreachable
vertices. The natural-valued SimpleGraph.dist is 0 there, so it would make distinct
vertices in different components adjacent: the square of the edgeless graph on two vertices
would be the complete graph.
def graphSquare (G : SimpleGraph α) : SimpleGraph α where
Adj u v := u ≠ v ∧ G.edist u v ≤ 2
symm.symm _ _ := fun ⟨hne, hd⟩ => ⟨hne.symm, by α:Type u_1inst✝¹:Fintype αinst✝:DecidableEq αG:SimpleGraph αx✝²:αx✝¹:αx✝:x✝² ≠ x✝¹ ∧ G.edist x✝² x✝¹ ≤ 2hne:x✝² ≠ x✝¹hd:G.edist x✝² x✝¹ ≤ 2⊢ G.edist x✝¹ x✝² ≤ 2 rwa [edist_comm α:Type u_1inst✝¹:Fintype αinst✝:DecidableEq αG:SimpleGraph αx✝²:αx✝¹:αx✝:x✝² ≠ x✝¹ ∧ G.edist x✝² x✝¹ ≤ 2hne:x✝² ≠ x✝¹hd:G.edist x✝² x✝¹ ≤ 2⊢ G.edist x✝² x✝¹ ≤ 2] α:Type u_1inst✝¹:Fintype αinst✝:DecidableEq αG:SimpleGraph αx✝²:αx✝¹:αx✝:x✝² ≠ x✝¹ ∧ G.edist x✝² x✝¹ ≤ 2hne:x✝² ≠ x✝¹hd:G.edist x✝² x✝¹ ≤ 2⊢ G.edist x✝² x✝¹ ≤ 2⟩
loopless.irrefl v := by α:Type u_1inst✝¹:Fintype αinst✝:DecidableEq αG:SimpleGraph αv:α⊢ ¬(v ≠ v ∧ G.edist v v ≤ 2) simp All goals completed! 🐙
Check whether four distinct vertices form an induced 4-cycle in G.
We test all three perfect-matching pairings of the four vertices to find
a cyclic ordering and verify that the induced subgraph has exactly those 4 edges.
noncomputable def isInducedC4 (G : SimpleGraph α) [DecidableRel G.Adj]
(a b c d : α) : Bool :=
-- Cyclic orderings up to symmetry: (a-b-c-d), (a-b-d-c), (a-c-b-d)
let check (p q r s : α) : Bool :=
G.Adj p q && G.Adj q r && G.Adj r s && G.Adj s p &&
!G.Adj p r && !G.Adj q s
check a b c d || check a b d c || check a c b d
Count of induced C₄ subgraphs of G. We count ordered 4-tuples (a,b,c,d)
of distinct vertices for which isInducedC4 G a b c d = true, then divide by
24 = 4!.
Why 24 (and not 8)? isInducedC4 tests all three perfect-matching
pairings of the four vertices, so any of the 4! = 24 orderings of a fixed
unordered induced 4-cycle satisfies the predicate. Dividing by 8 (the size
of the dihedral group D₄) would overcount each induced 4-cycle by a factor
of 3 — once for each of the three cyclic structures isInducedC4 accepts.
noncomputable def countInducedC4 (G : SimpleGraph α) [DecidableRel G.Adj] : ℕ :=
(∑ a : α, ∑ b : α, ∑ c : α, ∑ d : α,
if a ≠ b ∧ a ≠ c ∧ a ≠ d ∧ b ≠ c ∧ b ≠ d ∧ c ≠ d ∧
isInducedC4 G a b c d = true then 1 else 0) / 24def bfs_dist_aux (G : SimpleGraph α) [DecidableRel G.Adj] (target : α) : ℕ → ℕ → Finset α → ℕ
| 0, _, _ => 0
| fuel + 1, depth, reached =>
if target ∈ reached then depth
else bfs_dist_aux G target fuel (depth + 1) (G.bfsStep reached)Computable graph distance via BFS. Returns 0 if u = v or if v is unreachable from u.
def computable_dist (G : SimpleGraph α) [DecidableRel G.Adj] (u v : α) : ℕ :=
if u = v then 0
else bfs_dist_aux G v (Fintype.card α) 1 (G.bfsStep {u})
A computable version of distMin for a Finset of vertices.
def computableDistMin (G : SimpleGraph α) [DecidableRel G.Adj] (S : Finset α) : ℕ :=
let pairs := (S ×ˢ S).filter (fun p => p.1 ≠ p.2)
if h : pairs.Nonempty then
(pairs.image (fun p => computable_dist G p.1 p.2)).min' (Finset.Nonempty.image h _)
else 0Computable average distance as a rational.
def computable_avg_dist (G : SimpleGraph α) [DecidableRel G.Adj] : ℚ :=
if Fintype.card α > 1 then
(∑ u ∈ Finset.univ, ∑ v ∈ Finset.univ, (computable_dist G u v : ℚ)) /
((Fintype.card α : ℚ) * ((Fintype.card α : ℚ) - 1))
else 0
private lemma mem_iterate_bfsStep_dist_le (G : SimpleGraph α) [DecidableRel G.Adj]
(u w : α) (n : ℕ) (hw : w ∈ G.bfsStep^[n] {u}) : G.dist u w ≤ n := by α:Type u_1inst✝²:Fintype αinst✝¹:DecidableEq αG:SimpleGraph αinst✝:DecidableRel G.Adju:αw:αn:ℕhw:w ∈ G.bfsStep^[n] {u}⊢ G.dist u w ≤ n
induction n generalizing w with
| zero => zero α:Type u_1inst✝²:Fintype αinst✝¹:DecidableEq αG:SimpleGraph αinst✝:DecidableRel G.Adju:αw:αhw:w ∈ G.bfsStep^[0] {u}⊢ G.dist u w ≤ 0 simp at hw zero α:Type u_1inst✝²:Fintype αinst✝¹:DecidableEq αG:SimpleGraph αinst✝:DecidableRel G.Adju:αw:αhw:w = u⊢ G.dist u w ≤ 0; subst hw zero α:Type u_1inst✝²:Fintype αinst✝¹:DecidableEq αG:SimpleGraph αinst✝:DecidableRel G.Adjw:α⊢ G.dist w w ≤ 0; simp All goals completed! 🐙
| succ n ih => succ α:Type u_1inst✝²:Fintype αinst✝¹:DecidableEq αG:SimpleGraph αinst✝:DecidableRel G.Adju:αn:ℕih:∀ w ∈ G.bfsStep^[n] {u}, G.dist u w ≤ nw:αhw:w ∈ G.bfsStep^[n + 1] {u}⊢ G.dist u w ≤ n + 1
rw [Function.iterate_succ', succ α:Type u_1inst✝²:Fintype αinst✝¹:DecidableEq αG:SimpleGraph αinst✝:DecidableRel G.Adju:αn:ℕih:∀ w ∈ G.bfsStep^[n] {u}, G.dist u w ≤ nw:αhw:w ∈ (G.bfsStep ∘ G.bfsStep^[n]) {u}⊢ G.dist u w ≤ n + 1 succ α:Type u_1inst✝²:Fintype αinst✝¹:DecidableEq αG:SimpleGraph αinst✝:DecidableRel G.Adju:αn:ℕih:∀ w ∈ G.bfsStep^[n] {u}, G.dist u w ≤ nw:αhw:w ∈ G.bfsStep (G.bfsStep^[n] {u})⊢ G.dist u w ≤ n + 1 Function.comp succ α:Type u_1inst✝²:Fintype αinst✝¹:DecidableEq αG:SimpleGraph αinst✝:DecidableRel G.Adju:αn:ℕih:∀ w ∈ G.bfsStep^[n] {u}, G.dist u w ≤ nw:αhw:w ∈ G.bfsStep (G.bfsStep^[n] {u})⊢ G.dist u w ≤ n + 1 succ α:Type u_1inst✝²:Fintype αinst✝¹:DecidableEq αG:SimpleGraph αinst✝:DecidableRel G.Adju:αn:ℕih:∀ w ∈ G.bfsStep^[n] {u}, G.dist u w ≤ nw:αhw:w ∈ G.bfsStep (G.bfsStep^[n] {u})⊢ G.dist u w ≤ n + 1] at hwsucc α:Type u_1inst✝²:Fintype αinst✝¹:DecidableEq αG:SimpleGraph αinst✝:DecidableRel G.Adju:αn:ℕih:∀ w ∈ G.bfsStep^[n] {u}, G.dist u w ≤ nw:αhw:w ∈ G.bfsStep (G.bfsStep^[n] {u})⊢ G.dist u w ≤ n + 1
simp only [mem_bfsStep] at hw succ α:Type u_1inst✝²:Fintype αinst✝¹:DecidableEq αG:SimpleGraph αinst✝:DecidableRel G.Adju:αn:ℕih:∀ w ∈ G.bfsStep^[n] {u}, G.dist u w ≤ nw:αhw:w ∈ G.bfsStep^[n] {u} ∨ ∃ v ∈ G.bfsStep^[n] {u}, G.Adj v w⊢ G.dist u w ≤ n + 1
rcases hw with hw | ⟨a, ha_mem, hadj⟩ succ.inl α:Type u_1inst✝²:Fintype αinst✝¹:DecidableEq αG:SimpleGraph αinst✝:DecidableRel G.Adju:αn:ℕih:∀ w ∈ G.bfsStep^[n] {u}, G.dist u w ≤ nw:αhw:w ∈ G.bfsStep^[n] {u}⊢ G.dist u w ≤ n + 1succ.inr α:Type u_1inst✝²:Fintype αinst✝¹:DecidableEq αG:SimpleGraph αinst✝:DecidableRel G.Adju:αn:ℕih:∀ w ∈ G.bfsStep^[n] {u}, G.dist u w ≤ nw:αa:αha_mem:a ∈ G.bfsStep^[n] {u}hadj:G.Adj a w⊢ G.dist u w ≤ n + 1
· succ.inl α:Type u_1inst✝²:Fintype αinst✝¹:DecidableEq αG:SimpleGraph αinst✝:DecidableRel G.Adju:αn:ℕih:∀ w ∈ G.bfsStep^[n] {u}, G.dist u w ≤ nw:αhw:w ∈ G.bfsStep^[n] {u}⊢ G.dist u w ≤ n + 1 exact Nat.le_succ_of_le (ih w hw) All goals completed! 🐙
· succ.inr α:Type u_1inst✝²:Fintype αinst✝¹:DecidableEq αG:SimpleGraph αinst✝:DecidableRel G.Adju:αn:ℕih:∀ w ∈ G.bfsStep^[n] {u}, G.dist u w ≤ nw:αa:αha_mem:a ∈ G.bfsStep^[n] {u}hadj:G.Adj a w⊢ G.dist u w ≤ n + 1 by_cases ha : a = u pos α:Type u_1inst✝²:Fintype αinst✝¹:DecidableEq αG:SimpleGraph αinst✝:DecidableRel G.Adju:αn:ℕih:∀ w ∈ G.bfsStep^[n] {u}, G.dist u w ≤ nw:αa:αha_mem:a ∈ G.bfsStep^[n] {u}hadj:G.Adj a wha:a = u⊢ G.dist u w ≤ n + 1neg α:Type u_1inst✝²:Fintype αinst✝¹:DecidableEq αG:SimpleGraph αinst✝:DecidableRel G.Adju:αn:ℕih:∀ w ∈ G.bfsStep^[n] {u}, G.dist u w ≤ nw:αa:αha_mem:a ∈ G.bfsStep^[n] {u}hadj:G.Adj a wha:¬a = u⊢ G.dist u w ≤ n + 1
· pos α:Type u_1inst✝²:Fintype αinst✝¹:DecidableEq αG:SimpleGraph αinst✝:DecidableRel G.Adju:αn:ℕih:∀ w ∈ G.bfsStep^[n] {u}, G.dist u w ≤ nw:αa:αha_mem:a ∈ G.bfsStep^[n] {u}hadj:G.Adj a wha:a = u⊢ G.dist u w ≤ n + 1 subst ha pos α:Type u_1inst✝²:Fintype αinst✝¹:DecidableEq αG:SimpleGraph αinst✝:DecidableRel G.Adjn:ℕw:αa:αhadj:G.Adj a wih:∀ w ∈ G.bfsStep^[n] {a}, G.dist a w ≤ nha_mem:a ∈ G.bfsStep^[n] {a}⊢ G.dist a w ≤ n + 1
exact le_trans (dist_le (.cons hadj .nil))
(by α:Type u_1inst✝²:Fintype αinst✝¹:DecidableEq αG:SimpleGraph αinst✝:DecidableRel G.Adjn:ℕw:αa:αhadj:G.Adj a wih:∀ w ∈ G.bfsStep^[n] {a}, G.dist a w ≤ nha_mem:a ∈ G.bfsStep^[n] {a}⊢ (Walk.cons hadj Walk.nil).length ≤ n + 1 simp [Walk.length_cons] All goals completed! 🐙)
· neg α:Type u_1inst✝²:Fintype αinst✝¹:DecidableEq αG:SimpleGraph αinst✝:DecidableRel G.Adju:αn:ℕih:∀ w ∈ G.bfsStep^[n] {u}, G.dist u w ≤ nw:αa:αha_mem:a ∈ G.bfsStep^[n] {u}hadj:G.Adj a wha:¬a = u⊢ G.dist u w ≤ n + 1 by_cases hd : G.dist u a = 0 pos α:Type u_1inst✝²:Fintype αinst✝¹:DecidableEq αG:SimpleGraph αinst✝:DecidableRel G.Adju:αn:ℕih:∀ w ∈ G.bfsStep^[n] {u}, G.dist u w ≤ nw:αa:αha_mem:a ∈ G.bfsStep^[n] {u}hadj:G.Adj a wha:¬a = uhd:G.dist u a = 0⊢ G.dist u w ≤ n + 1neg α:Type u_1inst✝²:Fintype αinst✝¹:DecidableEq αG:SimpleGraph αinst✝:DecidableRel G.Adju:αn:ℕih:∀ w ∈ G.bfsStep^[n] {u}, G.dist u w ≤ nw:αa:αha_mem:a ∈ G.bfsStep^[n] {u}hadj:G.Adj a wha:¬a = uhd:¬G.dist u a = 0⊢ G.dist u w ≤ n + 1
· pos α:Type u_1inst✝²:Fintype αinst✝¹:DecidableEq αG:SimpleGraph αinst✝:DecidableRel G.Adju:αn:ℕih:∀ w ∈ G.bfsStep^[n] {u}, G.dist u w ≤ nw:αa:αha_mem:a ∈ G.bfsStep^[n] {u}hadj:G.Adj a wha:¬a = uhd:G.dist u a = 0⊢ G.dist u w ≤ n + 1 rw [dist_eq_zero_iff_eq_or_not_reachable pos α:Type u_1inst✝²:Fintype αinst✝¹:DecidableEq αG:SimpleGraph αinst✝:DecidableRel G.Adju:αn:ℕih:∀ w ∈ G.bfsStep^[n] {u}, G.dist u w ≤ nw:αa:αha_mem:a ∈ G.bfsStep^[n] {u}hadj:G.Adj a wha:¬a = uhd:u = a ∨ ¬G.Reachable u a⊢ G.dist u w ≤ n + 1 pos α:Type u_1inst✝²:Fintype αinst✝¹:DecidableEq αG:SimpleGraph αinst✝:DecidableRel G.Adju:αn:ℕih:∀ w ∈ G.bfsStep^[n] {u}, G.dist u w ≤ nw:αa:αha_mem:a ∈ G.bfsStep^[n] {u}hadj:G.Adj a wha:¬a = uhd:u = a ∨ ¬G.Reachable u a⊢ G.dist u w ≤ n + 1] at hdpos α:Type u_1inst✝²:Fintype αinst✝¹:DecidableEq αG:SimpleGraph αinst✝:DecidableRel G.Adju:αn:ℕih:∀ w ∈ G.bfsStep^[n] {u}, G.dist u w ≤ nw:αa:αha_mem:a ∈ G.bfsStep^[n] {u}hadj:G.Adj a wha:¬a = uhd:u = a ∨ ¬G.Reachable u a⊢ G.dist u w ≤ n + 1
rcases hd with rfl | hd pos.inl α:Type u_1inst✝²:Fintype αinst✝¹:DecidableEq αG:SimpleGraph αinst✝:DecidableRel G.Adju:αn:ℕih:∀ w ∈ G.bfsStep^[n] {u}, G.dist u w ≤ nw:αha_mem:u ∈ G.bfsStep^[n] {u}hadj:G.Adj u wha:¬u = u⊢ G.dist u w ≤ n + 1pos.inr α:Type u_1inst✝²:Fintype αinst✝¹:DecidableEq αG:SimpleGraph αinst✝:DecidableRel G.Adju:αn:ℕih:∀ w ∈ G.bfsStep^[n] {u}, G.dist u w ≤ nw:αa:αha_mem:a ∈ G.bfsStep^[n] {u}hadj:G.Adj a wha:¬a = uhd:¬G.Reachable u a⊢ G.dist u w ≤ n + 1
· pos.inl α:Type u_1inst✝²:Fintype αinst✝¹:DecidableEq αG:SimpleGraph αinst✝:DecidableRel G.Adju:αn:ℕih:∀ w ∈ G.bfsStep^[n] {u}, G.dist u w ≤ nw:αha_mem:u ∈ G.bfsStep^[n] {u}hadj:G.Adj u wha:¬u = u⊢ G.dist u w ≤ n + 1 exact absurd rfl ha All goals completed! 🐙
· pos.inr α:Type u_1inst✝²:Fintype αinst✝¹:DecidableEq αG:SimpleGraph αinst✝:DecidableRel G.Adju:αn:ℕih:∀ w ∈ G.bfsStep^[n] {u}, G.dist u w ≤ nw:αa:αha_mem:a ∈ G.bfsStep^[n] {u}hadj:G.Adj a wha:¬a = uhd:¬G.Reachable u a⊢ G.dist u w ≤ n + 1 have : ¬G.Reachable u w := fun hr =>
hd (hr.elim (fun p => (p.append (.cons hadj.symm .nil)).reachable)) pos.inr α:Type u_1inst✝²:Fintype αinst✝¹:DecidableEq αG:SimpleGraph αinst✝:DecidableRel G.Adju:αn:ℕih:∀ w ∈ G.bfsStep^[n] {u}, G.dist u w ≤ nw:αa:αha_mem:a ∈ G.bfsStep^[n] {u}hadj:G.Adj a wha:¬a = uhd:¬G.Reachable u athis:¬G.Reachable u w⊢ G.dist u w ≤ n + 1
rw [dist_eq_zero_of_not_reachable this pos.inr α:Type u_1inst✝²:Fintype αinst✝¹:DecidableEq αG:SimpleGraph αinst✝:DecidableRel G.Adju:αn:ℕih:∀ w ∈ G.bfsStep^[n] {u}, G.dist u w ≤ nw:αa:αha_mem:a ∈ G.bfsStep^[n] {u}hadj:G.Adj a wha:¬a = uhd:¬G.Reachable u athis:¬G.Reachable u w⊢ 0 ≤ n + 1 pos.inr α:Type u_1inst✝²:Fintype αinst✝¹:DecidableEq αG:SimpleGraph αinst✝:DecidableRel G.Adju:αn:ℕih:∀ w ∈ G.bfsStep^[n] {u}, G.dist u w ≤ nw:αa:αha_mem:a ∈ G.bfsStep^[n] {u}hadj:G.Adj a wha:¬a = uhd:¬G.Reachable u athis:¬G.Reachable u w⊢ 0 ≤ n + 1]pos.inr α:Type u_1inst✝²:Fintype αinst✝¹:DecidableEq αG:SimpleGraph αinst✝:DecidableRel G.Adju:αn:ℕih:∀ w ∈ G.bfsStep^[n] {u}, G.dist u w ≤ nw:αa:αha_mem:a ∈ G.bfsStep^[n] {u}hadj:G.Adj a wha:¬a = uhd:¬G.Reachable u athis:¬G.Reachable u w⊢ 0 ≤ n + 1; omega All goals completed! 🐙
· neg α:Type u_1inst✝²:Fintype αinst✝¹:DecidableEq αG:SimpleGraph αinst✝:DecidableRel G.Adju:αn:ℕih:∀ w ∈ G.bfsStep^[n] {u}, G.dist u w ≤ nw:αa:αha_mem:a ∈ G.bfsStep^[n] {u}hadj:G.Adj a wha:¬a = uhd:¬G.dist u a = 0⊢ G.dist u w ≤ n + 1 obtain ⟨p, hp⟩ := exists_walk_of_dist_ne_zero hd neg α:Type u_1inst✝²:Fintype αinst✝¹:DecidableEq αG:SimpleGraph αinst✝:DecidableRel G.Adju:αn:ℕih:∀ w ∈ G.bfsStep^[n] {u}, G.dist u w ≤ nw:αa:αha_mem:a ∈ G.bfsStep^[n] {u}hadj:G.Adj a wha:¬a = uhd:¬G.dist u a = 0p:G.Walk u ahp:p.length = G.dist u a⊢ G.dist u w ≤ n + 1
have ha_dist := ih a ha_mem neg α:Type u_1inst✝²:Fintype αinst✝¹:DecidableEq αG:SimpleGraph αinst✝:DecidableRel G.Adju:αn:ℕih:∀ w ∈ G.bfsStep^[n] {u}, G.dist u w ≤ nw:αa:αha_mem:a ∈ G.bfsStep^[n] {u}hadj:G.Adj a wha:¬a = uhd:¬G.dist u a = 0p:G.Walk u ahp:p.length = G.dist u aha_dist:G.dist u a ≤ n⊢ G.dist u w ≤ n + 1
exact le_trans (dist_le (p.append (.cons hadj .nil)))
(by α:Type u_1inst✝²:Fintype αinst✝¹:DecidableEq αG:SimpleGraph αinst✝:DecidableRel G.Adju:αn:ℕih:∀ w ∈ G.bfsStep^[n] {u}, G.dist u w ≤ nw:αa:αha_mem:a ∈ G.bfsStep^[n] {u}hadj:G.Adj a wha:¬a = uhd:¬G.dist u a = 0p:G.Walk u ahp:p.length = G.dist u aha_dist:G.dist u a ≤ n⊢ (p.append (Walk.cons hadj Walk.nil)).length ≤ n + 1 simp [Walk.length_append, Walk.length_cons, Walk.length_nil, hp] α:Type u_1inst✝²:Fintype αinst✝¹:DecidableEq αG:SimpleGraph αinst✝:DecidableRel G.Adju:αn:ℕih:∀ w ∈ G.bfsStep^[n] {u}, G.dist u w ≤ nw:αa:αha_mem:a ∈ G.bfsStep^[n] {u}hadj:G.Adj a wha:¬a = uhd:¬G.dist u a = 0p:G.Walk u ahp:p.length = G.dist u aha_dist:G.dist u a ≤ n⊢ G.dist u a ≤ n; omega All goals completed! 🐙)
private lemma dist_le_mem_iterate_bfsStep (G : SimpleGraph α) [DecidableRel G.Adj]
(u w : α) (n : ℕ) (hdist : G.dist u w ≤ n) (hreach : w = u ∨ G.Reachable u w) :
w ∈ G.bfsStep^[n] {u} := by α:Type u_1inst✝²:Fintype αinst✝¹:DecidableEq αG:SimpleGraph αinst✝:DecidableRel G.Adju:αw:αn:ℕhdist:G.dist u w ≤ nhreach:w = u ∨ G.Reachable u w⊢ w ∈ G.bfsStep^[n] {u}
induction n generalizing w with
| zero => zero α:Type u_1inst✝²:Fintype αinst✝¹:DecidableEq αG:SimpleGraph αinst✝:DecidableRel G.Adju:αw:αhdist:G.dist u w ≤ 0hreach:w = u ∨ G.Reachable u w⊢ w ∈ G.bfsStep^[0] {u}
rcases hreach with rfl | hr zero.inl α:Type u_1inst✝²:Fintype αinst✝¹:DecidableEq αG:SimpleGraph αinst✝:DecidableRel G.Adjw:αhdist:G.dist w w ≤ 0⊢ w ∈ G.bfsStep^[0] {w}zero.inr α:Type u_1inst✝²:Fintype αinst✝¹:DecidableEq αG:SimpleGraph αinst✝:DecidableRel G.Adju:αw:αhdist:G.dist u w ≤ 0hr:G.Reachable u w⊢ w ∈ G.bfsStep^[0] {u}
· zero.inl α:Type u_1inst✝²:Fintype αinst✝¹:DecidableEq αG:SimpleGraph αinst✝:DecidableRel G.Adjw:αhdist:G.dist w w ≤ 0⊢ w ∈ G.bfsStep^[0] {w} exact Finset.mem_singleton_self _ All goals completed! 🐙
· zero.inr α:Type u_1inst✝²:Fintype αinst✝¹:DecidableEq αG:SimpleGraph αinst✝:DecidableRel G.Adju:αw:αhdist:G.dist u w ≤ 0hr:G.Reachable u w⊢ w ∈ G.bfsStep^[0] {u} have h0 := Nat.le_zero.mp hdist zero.inr α:Type u_1inst✝²:Fintype αinst✝¹:DecidableEq αG:SimpleGraph αinst✝:DecidableRel G.Adju:αw:αhdist:G.dist u w ≤ 0hr:G.Reachable u wh0:G.dist u w = 0⊢ w ∈ G.bfsStep^[0] {u}
rw [dist_eq_zero_iff_eq_or_not_reachable zero.inr α:Type u_1inst✝²:Fintype αinst✝¹:DecidableEq αG:SimpleGraph αinst✝:DecidableRel G.Adju:αw:αhdist:G.dist u w ≤ 0hr:G.Reachable u wh0:u = w ∨ ¬G.Reachable u w⊢ w ∈ G.bfsStep^[0] {u} zero.inr α:Type u_1inst✝²:Fintype αinst✝¹:DecidableEq αG:SimpleGraph αinst✝:DecidableRel G.Adju:αw:αhdist:G.dist u w ≤ 0hr:G.Reachable u wh0:u = w ∨ ¬G.Reachable u w⊢ w ∈ G.bfsStep^[0] {u}] at h0 zero.inr α:Type u_1inst✝²:Fintype αinst✝¹:DecidableEq αG:SimpleGraph αinst✝:DecidableRel G.Adju:αw:αhdist:G.dist u w ≤ 0hr:G.Reachable u wh0:u = w ∨ ¬G.Reachable u w⊢ w ∈ G.bfsStep^[0] {u}
rcases h0 with h0 | h0 zero.inr.inl α:Type u_1inst✝²:Fintype αinst✝¹:DecidableEq αG:SimpleGraph αinst✝:DecidableRel G.Adju:αw:αhdist:G.dist u w ≤ 0hr:G.Reachable u wh0:u = w⊢ w ∈ G.bfsStep^[0] {u}zero.inr.inr α:Type u_1inst✝²:Fintype αinst✝¹:DecidableEq αG:SimpleGraph αinst✝:DecidableRel G.Adju:αw:αhdist:G.dist u w ≤ 0hr:G.Reachable u wh0:¬G.Reachable u w⊢ w ∈ G.bfsStep^[0] {u}
· zero.inr.inl α:Type u_1inst✝²:Fintype αinst✝¹:DecidableEq αG:SimpleGraph αinst✝:DecidableRel G.Adju:αw:αhdist:G.dist u w ≤ 0hr:G.Reachable u wh0:u = w⊢ w ∈ G.bfsStep^[0] {u} subst h0 zero.inr.inl α:Type u_1inst✝²:Fintype αinst✝¹:DecidableEq αG:SimpleGraph αinst✝:DecidableRel G.Adju:αhdist:G.dist u u ≤ 0hr:G.Reachable u u⊢ u ∈ G.bfsStep^[0] {u}; exact Finset.mem_singleton_self _ All goals completed! 🐙
· zero.inr.inr α:Type u_1inst✝²:Fintype αinst✝¹:DecidableEq αG:SimpleGraph αinst✝:DecidableRel G.Adju:αw:αhdist:G.dist u w ≤ 0hr:G.Reachable u wh0:¬G.Reachable u w⊢ w ∈ G.bfsStep^[0] {u} exact absurd hr h0 All goals completed! 🐙
| succ n ih => succ α:Type u_1inst✝²:Fintype αinst✝¹:DecidableEq αG:SimpleGraph αinst✝:DecidableRel G.Adju:αn:ℕih:∀ (w : α), G.dist u w ≤ n → w = u ∨ G.Reachable u w → w ∈ G.bfsStep^[n] {u}w:αhdist:G.dist u w ≤ n + 1hreach:w = u ∨ G.Reachable u w⊢ w ∈ G.bfsStep^[n + 1] {u}
rw [Function.iterate_succ', succ α:Type u_1inst✝²:Fintype αinst✝¹:DecidableEq αG:SimpleGraph αinst✝:DecidableRel G.Adju:αn:ℕih:∀ (w : α), G.dist u w ≤ n → w = u ∨ G.Reachable u w → w ∈ G.bfsStep^[n] {u}w:αhdist:G.dist u w ≤ n + 1hreach:w = u ∨ G.Reachable u w⊢ w ∈ (G.bfsStep ∘ G.bfsStep^[n]) {u} succ α:Type u_1inst✝²:Fintype αinst✝¹:DecidableEq αG:SimpleGraph αinst✝:DecidableRel G.Adju:αn:ℕih:∀ (w : α), G.dist u w ≤ n → w = u ∨ G.Reachable u w → w ∈ G.bfsStep^[n] {u}w:αhdist:G.dist u w ≤ n + 1hreach:w = u ∨ G.Reachable u w⊢ w ∈ G.bfsStep (G.bfsStep^[n] {u}) Function.comp succ α:Type u_1inst✝²:Fintype αinst✝¹:DecidableEq αG:SimpleGraph αinst✝:DecidableRel G.Adju:αn:ℕih:∀ (w : α), G.dist u w ≤ n → w = u ∨ G.Reachable u w → w ∈ G.bfsStep^[n] {u}w:αhdist:G.dist u w ≤ n + 1hreach:w = u ∨ G.Reachable u w⊢ w ∈ G.bfsStep (G.bfsStep^[n] {u})succ α:Type u_1inst✝²:Fintype αinst✝¹:DecidableEq αG:SimpleGraph αinst✝:DecidableRel G.Adju:αn:ℕih:∀ (w : α), G.dist u w ≤ n → w = u ∨ G.Reachable u w → w ∈ G.bfsStep^[n] {u}w:αhdist:G.dist u w ≤ n + 1hreach:w = u ∨ G.Reachable u w⊢ w ∈ G.bfsStep (G.bfsStep^[n] {u})]succ α:Type u_1inst✝²:Fintype αinst✝¹:DecidableEq αG:SimpleGraph αinst✝:DecidableRel G.Adju:αn:ℕih:∀ (w : α), G.dist u w ≤ n → w = u ∨ G.Reachable u w → w ∈ G.bfsStep^[n] {u}w:αhdist:G.dist u w ≤ n + 1hreach:w = u ∨ G.Reachable u w⊢ w ∈ G.bfsStep (G.bfsStep^[n] {u})
simp only [mem_bfsStep] succ α:Type u_1inst✝²:Fintype αinst✝¹:DecidableEq αG:SimpleGraph αinst✝:DecidableRel G.Adju:αn:ℕih:∀ (w : α), G.dist u w ≤ n → w = u ∨ G.Reachable u w → w ∈ G.bfsStep^[n] {u}w:αhdist:G.dist u w ≤ n + 1hreach:w = u ∨ G.Reachable u w⊢ w ∈ G.bfsStep^[n] {u} ∨ ∃ v ∈ G.bfsStep^[n] {u}, G.Adj v w
by_cases hle : G.dist u w ≤ n pos α:Type u_1inst✝²:Fintype αinst✝¹:DecidableEq αG:SimpleGraph αinst✝:DecidableRel G.Adju:αn:ℕih:∀ (w : α), G.dist u w ≤ n → w = u ∨ G.Reachable u w → w ∈ G.bfsStep^[n] {u}w:αhdist:G.dist u w ≤ n + 1hreach:w = u ∨ G.Reachable u whle:G.dist u w ≤ n⊢ w ∈ G.bfsStep^[n] {u} ∨ ∃ v ∈ G.bfsStep^[n] {u}, G.Adj v wneg α:Type u_1inst✝²:Fintype αinst✝¹:DecidableEq αG:SimpleGraph αinst✝:DecidableRel G.Adju:αn:ℕih:∀ (w : α), G.dist u w ≤ n → w = u ∨ G.Reachable u w → w ∈ G.bfsStep^[n] {u}w:αhdist:G.dist u w ≤ n + 1hreach:w = u ∨ G.Reachable u whle:¬G.dist u w ≤ n⊢ w ∈ G.bfsStep^[n] {u} ∨ ∃ v ∈ G.bfsStep^[n] {u}, G.Adj v w
· pos α:Type u_1inst✝²:Fintype αinst✝¹:DecidableEq αG:SimpleGraph αinst✝:DecidableRel G.Adju:αn:ℕih:∀ (w : α), G.dist u w ≤ n → w = u ∨ G.Reachable u w → w ∈ G.bfsStep^[n] {u}w:αhdist:G.dist u w ≤ n + 1hreach:w = u ∨ G.Reachable u whle:G.dist u w ≤ n⊢ w ∈ G.bfsStep^[n] {u} ∨ ∃ v ∈ G.bfsStep^[n] {u}, G.Adj v w left pos α:Type u_1inst✝²:Fintype αinst✝¹:DecidableEq αG:SimpleGraph αinst✝:DecidableRel G.Adju:αn:ℕih:∀ (w : α), G.dist u w ≤ n → w = u ∨ G.Reachable u w → w ∈ G.bfsStep^[n] {u}w:αhdist:G.dist u w ≤ n + 1hreach:w = u ∨ G.Reachable u whle:G.dist u w ≤ n⊢ w ∈ G.bfsStep^[n] {u}; exact ih w hle hreach All goals completed! 🐙
· neg α:Type u_1inst✝²:Fintype αinst✝¹:DecidableEq αG:SimpleGraph αinst✝:DecidableRel G.Adju:αn:ℕih:∀ (w : α), G.dist u w ≤ n → w = u ∨ G.Reachable u w → w ∈ G.bfsStep^[n] {u}w:αhdist:G.dist u w ≤ n + 1hreach:w = u ∨ G.Reachable u whle:¬G.dist u w ≤ n⊢ w ∈ G.bfsStep^[n] {u} ∨ ∃ v ∈ G.bfsStep^[n] {u}, G.Adj v w right neg α:Type u_1inst✝²:Fintype αinst✝¹:DecidableEq αG:SimpleGraph αinst✝:DecidableRel G.Adju:αn:ℕih:∀ (w : α), G.dist u w ≤ n → w = u ∨ G.Reachable u w → w ∈ G.bfsStep^[n] {u}w:αhdist:G.dist u w ≤ n + 1hreach:w = u ∨ G.Reachable u whle:¬G.dist u w ≤ n⊢ ∃ v ∈ G.bfsStep^[n] {u}, G.Adj v w
have hdist_eq : G.dist u w = n + 1 := by α:Type u_1inst✝²:Fintype αinst✝¹:DecidableEq αG:SimpleGraph αinst✝:DecidableRel G.Adju:αw:αn:ℕhdist:G.dist u w ≤ nhreach:w = u ∨ G.Reachable u w⊢ w ∈ G.bfsStep^[n] {u} neg α:Type u_1inst✝²:Fintype αinst✝¹:DecidableEq αG:SimpleGraph αinst✝:DecidableRel G.Adju:αn:ℕih:∀ (w : α), G.dist u w ≤ n → w = u ∨ G.Reachable u w → w ∈ G.bfsStep^[n] {u}w:αhdist:G.dist u w ≤ n + 1hreach:w = u ∨ G.Reachable u whle:¬G.dist u w ≤ nhdist_eq:G.dist u w = n + 1⊢ ∃ v ∈ G.bfsStep^[n] {u}, G.Adj v w omeganeg α:Type u_1inst✝²:Fintype αinst✝¹:DecidableEq αG:SimpleGraph αinst✝:DecidableRel G.Adju:αn:ℕih:∀ (w : α), G.dist u w ≤ n → w = u ∨ G.Reachable u w → w ∈ G.bfsStep^[n] {u}w:αhdist:G.dist u w ≤ n + 1hreach:w = u ∨ G.Reachable u whle:¬G.dist u w ≤ nhdist_eq:G.dist u w = n + 1⊢ ∃ v ∈ G.bfsStep^[n] {u}, G.Adj v wneg α:Type u_1inst✝²:Fintype αinst✝¹:DecidableEq αG:SimpleGraph αinst✝:DecidableRel G.Adju:αn:ℕih:∀ (w : α), G.dist u w ≤ n → w = u ∨ G.Reachable u w → w ∈ G.bfsStep^[n] {u}w:αhdist:G.dist u w ≤ n + 1hreach:w = u ∨ G.Reachable u whle:¬G.dist u w ≤ nhdist_eq:G.dist u w = n + 1⊢ ∃ v ∈ G.bfsStep^[n] {u}, G.Adj v w
obtain ⟨p, hp⟩ := exists_walk_of_dist_ne_zero (by α:Type u_1inst✝²:Fintype αinst✝¹:DecidableEq αG:SimpleGraph αinst✝:DecidableRel G.Adju:αn:ℕih:∀ (w : α), G.dist u w ≤ n → w = u ∨ G.Reachable u w → w ∈ G.bfsStep^[n] {u}w:αhdist:G.dist u w ≤ n + 1hreach:w = u ∨ G.Reachable u whle:¬G.dist u w ≤ nhdist_eq:G.dist u w = n + 1⊢ G.dist u w ≠ 0 neg α:Type u_1inst✝²:Fintype αinst✝¹:DecidableEq αG:SimpleGraph αinst✝:DecidableRel G.Adju:αn:ℕih:∀ (w : α), G.dist u w ≤ n → w = u ∨ G.Reachable u w → w ∈ G.bfsStep^[n] {u}w:αhdist:G.dist u w ≤ n + 1hreach:w = u ∨ G.Reachable u whle:¬G.dist u w ≤ nhdist_eq:G.dist u w = n + 1p:G.Walk u whp:p.length = G.dist u w⊢ ∃ v ∈ G.bfsStep^[n] {u}, G.Adj v w omega All goals completed! 🐙neg α:Type u_1inst✝²:Fintype αinst✝¹:DecidableEq αG:SimpleGraph αinst✝:DecidableRel G.Adju:αn:ℕih:∀ (w : α), G.dist u w ≤ n → w = u ∨ G.Reachable u w → w ∈ G.bfsStep^[n] {u}w:αhdist:G.dist u w ≤ n + 1hreach:w = u ∨ G.Reachable u whle:¬G.dist u w ≤ nhdist_eq:G.dist u w = n + 1p:G.Walk u whp:p.length = G.dist u w⊢ ∃ v ∈ G.bfsStep^[n] {u}, G.Adj v w : G.dist u w ≠ 0)neg α:Type u_1inst✝²:Fintype αinst✝¹:DecidableEq αG:SimpleGraph αinst✝:DecidableRel G.Adju:αn:ℕih:∀ (w : α), G.dist u w ≤ n → w = u ∨ G.Reachable u w → w ∈ G.bfsStep^[n] {u}w:αhdist:G.dist u w ≤ n + 1hreach:w = u ∨ G.Reachable u whle:¬G.dist u w ≤ nhdist_eq:G.dist u w = n + 1p:G.Walk u whp:p.length = G.dist u w⊢ ∃ v ∈ G.bfsStep^[n] {u}, G.Adj v w
have hlen : p.length = n + 1 := by α:Type u_1inst✝²:Fintype αinst✝¹:DecidableEq αG:SimpleGraph αinst✝:DecidableRel G.Adju:αw:αn:ℕhdist:G.dist u w ≤ nhreach:w = u ∨ G.Reachable u w⊢ w ∈ G.bfsStep^[n] {u} neg α:Type u_1inst✝²:Fintype αinst✝¹:DecidableEq αG:SimpleGraph αinst✝:DecidableRel G.Adju:αn:ℕih:∀ (w : α), G.dist u w ≤ n → w = u ∨ G.Reachable u w → w ∈ G.bfsStep^[n] {u}w:αhdist:G.dist u w ≤ n + 1hreach:w = u ∨ G.Reachable u whle:¬G.dist u w ≤ nhdist_eq:G.dist u w = n + 1p:G.Walk u whp:p.length = G.dist u whlen:p.length = n + 1⊢ ∃ v ∈ G.bfsStep^[n] {u}, G.Adj v w omeganeg α:Type u_1inst✝²:Fintype αinst✝¹:DecidableEq αG:SimpleGraph αinst✝:DecidableRel G.Adju:αn:ℕih:∀ (w : α), G.dist u w ≤ n → w = u ∨ G.Reachable u w → w ∈ G.bfsStep^[n] {u}w:αhdist:G.dist u w ≤ n + 1hreach:w = u ∨ G.Reachable u whle:¬G.dist u w ≤ nhdist_eq:G.dist u w = n + 1p:G.Walk u whp:p.length = G.dist u whlen:p.length = n + 1⊢ ∃ v ∈ G.bfsStep^[n] {u}, G.Adj v wneg α:Type u_1inst✝²:Fintype αinst✝¹:DecidableEq αG:SimpleGraph αinst✝:DecidableRel G.Adju:αn:ℕih:∀ (w : α), G.dist u w ≤ n → w = u ∨ G.Reachable u w → w ∈ G.bfsStep^[n] {u}w:αhdist:G.dist u w ≤ n + 1hreach:w = u ∨ G.Reachable u whle:¬G.dist u w ≤ nhdist_eq:G.dist u w = n + 1p:G.Walk u whp:p.length = G.dist u whlen:p.length = n + 1⊢ ∃ v ∈ G.bfsStep^[n] {u}, G.Adj v w
refine ⟨p.getVert n, ?_, ?_⟩ neg.refine_1 α:Type u_1inst✝²:Fintype αinst✝¹:DecidableEq αG:SimpleGraph αinst✝:DecidableRel G.Adju:αn:ℕih:∀ (w : α), G.dist u w ≤ n → w = u ∨ G.Reachable u w → w ∈ G.bfsStep^[n] {u}w:αhdist:G.dist u w ≤ n + 1hreach:w = u ∨ G.Reachable u whle:¬G.dist u w ≤ nhdist_eq:G.dist u w = n + 1p:G.Walk u whp:p.length = G.dist u whlen:p.length = n + 1⊢ p.getVert n ∈ G.bfsStep^[n] {u}neg.refine_2 α:Type u_1inst✝²:Fintype αinst✝¹:DecidableEq αG:SimpleGraph αinst✝:DecidableRel G.Adju:αn:ℕih:∀ (w : α), G.dist u w ≤ n → w = u ∨ G.Reachable u w → w ∈ G.bfsStep^[n] {u}w:αhdist:G.dist u w ≤ n + 1hreach:w = u ∨ G.Reachable u whle:¬G.dist u w ≤ nhdist_eq:G.dist u w = n + 1p:G.Walk u whp:p.length = G.dist u whlen:p.length = n + 1⊢ G.Adj (p.getVert n) w
· neg.refine_1 α:Type u_1inst✝²:Fintype αinst✝¹:DecidableEq αG:SimpleGraph αinst✝:DecidableRel G.Adju:αn:ℕih:∀ (w : α), G.dist u w ≤ n → w = u ∨ G.Reachable u w → w ∈ G.bfsStep^[n] {u}w:αhdist:G.dist u w ≤ n + 1hreach:w = u ∨ G.Reachable u whle:¬G.dist u w ≤ nhdist_eq:G.dist u w = n + 1p:G.Walk u whp:p.length = G.dist u whlen:p.length = n + 1⊢ p.getVert n ∈ G.bfsStep^[n] {u} exact ih _ (le_trans (dist_le (p.take n))
(by α:Type u_1inst✝²:Fintype αinst✝¹:DecidableEq αG:SimpleGraph αinst✝:DecidableRel G.Adju:αn:ℕih:∀ (w : α), G.dist u w ≤ n → w = u ∨ G.Reachable u w → w ∈ G.bfsStep^[n] {u}w:αhdist:G.dist u w ≤ n + 1hreach:w = u ∨ G.Reachable u whle:¬G.dist u w ≤ nhdist_eq:G.dist u w = n + 1p:G.Walk u whp:p.length = G.dist u whlen:p.length = n + 1⊢ (p.take n).length ≤ n rw [Walk.take_length α:Type u_1inst✝²:Fintype αinst✝¹:DecidableEq αG:SimpleGraph αinst✝:DecidableRel G.Adju:αn:ℕih:∀ (w : α), G.dist u w ≤ n → w = u ∨ G.Reachable u w → w ∈ G.bfsStep^[n] {u}w:αhdist:G.dist u w ≤ n + 1hreach:w = u ∨ G.Reachable u whle:¬G.dist u w ≤ nhdist_eq:G.dist u w = n + 1p:G.Walk u whp:p.length = G.dist u whlen:p.length = n + 1⊢ min n p.length ≤ n α:Type u_1inst✝²:Fintype αinst✝¹:DecidableEq αG:SimpleGraph αinst✝:DecidableRel G.Adju:αn:ℕih:∀ (w : α), G.dist u w ≤ n → w = u ∨ G.Reachable u w → w ∈ G.bfsStep^[n] {u}w:αhdist:G.dist u w ≤ n + 1hreach:w = u ∨ G.Reachable u whle:¬G.dist u w ≤ nhdist_eq:G.dist u w = n + 1p:G.Walk u whp:p.length = G.dist u whlen:p.length = n + 1⊢ min n p.length ≤ n] α:Type u_1inst✝²:Fintype αinst✝¹:DecidableEq αG:SimpleGraph αinst✝:DecidableRel G.Adju:αn:ℕih:∀ (w : α), G.dist u w ≤ n → w = u ∨ G.Reachable u w → w ∈ G.bfsStep^[n] {u}w:αhdist:G.dist u w ≤ n + 1hreach:w = u ∨ G.Reachable u whle:¬G.dist u w ≤ nhdist_eq:G.dist u w = n + 1p:G.Walk u whp:p.length = G.dist u whlen:p.length = n + 1⊢ min n p.length ≤ n; omega All goals completed! 🐙)) (Or.inr (p.take n).reachable)
· neg.refine_2 α:Type u_1inst✝²:Fintype αinst✝¹:DecidableEq αG:SimpleGraph αinst✝:DecidableRel G.Adju:αn:ℕih:∀ (w : α), G.dist u w ≤ n → w = u ∨ G.Reachable u w → w ∈ G.bfsStep^[n] {u}w:αhdist:G.dist u w ≤ n + 1hreach:w = u ∨ G.Reachable u whle:¬G.dist u w ≤ nhdist_eq:G.dist u w = n + 1p:G.Walk u whp:p.length = G.dist u whlen:p.length = n + 1⊢ G.Adj (p.getVert n) w have := p.adj_getVert_succ (show n < p.length from by α:Type u_1inst✝²:Fintype αinst✝¹:DecidableEq αG:SimpleGraph αinst✝:DecidableRel G.Adju:αn:ℕih:∀ (w : α), G.dist u w ≤ n → w = u ∨ G.Reachable u w → w ∈ G.bfsStep^[n] {u}w:αhdist:G.dist u w ≤ n + 1hreach:w = u ∨ G.Reachable u whle:¬G.dist u w ≤ nhdist_eq:G.dist u w = n + 1p:G.Walk u whp:p.length = G.dist u whlen:p.length = n + 1⊢ n < p.length neg.refine_2 α:Type u_1inst✝²:Fintype αinst✝¹:DecidableEq αG:SimpleGraph αinst✝:DecidableRel G.Adju:αn:ℕih:∀ (w : α), G.dist u w ≤ n → w = u ∨ G.Reachable u w → w ∈ G.bfsStep^[n] {u}w:αhdist:G.dist u w ≤ n + 1hreach:w = u ∨ G.Reachable u whle:¬G.dist u w ≤ nhdist_eq:G.dist u w = n + 1p:G.Walk u whp:p.length = G.dist u whlen:p.length = n + 1this:G.Adj (p.getVert n) (p.getVert (n + 1))⊢ G.Adj (p.getVert n) w omega All goals completed! 🐙neg.refine_2 α:Type u_1inst✝²:Fintype αinst✝¹:DecidableEq αG:SimpleGraph αinst✝:DecidableRel G.Adju:αn:ℕih:∀ (w : α), G.dist u w ≤ n → w = u ∨ G.Reachable u w → w ∈ G.bfsStep^[n] {u}w:αhdist:G.dist u w ≤ n + 1hreach:w = u ∨ G.Reachable u whle:¬G.dist u w ≤ nhdist_eq:G.dist u w = n + 1p:G.Walk u whp:p.length = G.dist u whlen:p.length = n + 1this:G.Adj (p.getVert n) (p.getVert (n + 1))⊢ G.Adj (p.getVert n) w)neg.refine_2 α:Type u_1inst✝²:Fintype αinst✝¹:DecidableEq αG:SimpleGraph αinst✝:DecidableRel G.Adju:αn:ℕih:∀ (w : α), G.dist u w ≤ n → w = u ∨ G.Reachable u w → w ∈ G.bfsStep^[n] {u}w:αhdist:G.dist u w ≤ n + 1hreach:w = u ∨ G.Reachable u whle:¬G.dist u w ≤ nhdist_eq:G.dist u w = n + 1p:G.Walk u whp:p.length = G.dist u whlen:p.length = n + 1this:G.Adj (p.getVert n) (p.getVert (n + 1))⊢ G.Adj (p.getVert n) w
rwa [show n + 1 = p.length from by α:Type u_1inst✝²:Fintype αinst✝¹:DecidableEq αG:SimpleGraph αinst✝:DecidableRel G.Adju:αn:ℕih:∀ (w : α), G.dist u w ≤ n → w = u ∨ G.Reachable u w → w ∈ G.bfsStep^[n] {u}w:αhdist:G.dist u w ≤ n + 1hreach:w = u ∨ G.Reachable u whle:¬G.dist u w ≤ nhdist_eq:G.dist u w = n + 1p:G.Walk u whp:p.length = G.dist u whlen:p.length = n + 1this:G.Adj (p.getVert n) (p.getVert (n + 1))⊢ n + 1 = p.length omega All goals completed! 🐙, p.getVert_length neg.refine_2 α:Type u_1inst✝²:Fintype αinst✝¹:DecidableEq αG:SimpleGraph αinst✝:DecidableRel G.Adju:αn:ℕih:∀ (w : α), G.dist u w ≤ n → w = u ∨ G.Reachable u w → w ∈ G.bfsStep^[n] {u}w:αhdist:G.dist u w ≤ n + 1hreach:w = u ∨ G.Reachable u whle:¬G.dist u w ≤ nhdist_eq:G.dist u w = n + 1p:G.Walk u whp:p.length = G.dist u whlen:p.length = n + 1this:G.Adj (p.getVert n) w⊢ G.Adj (p.getVert n) w] neg.refine_2 α:Type u_1inst✝²:Fintype αinst✝¹:DecidableEq αG:SimpleGraph αinst✝:DecidableRel G.Adju:αn:ℕih:∀ (w : α), G.dist u w ≤ n → w = u ∨ G.Reachable u w → w ∈ G.bfsStep^[n] {u}w:αhdist:G.dist u w ≤ n + 1hreach:w = u ∨ G.Reachable u whle:¬G.dist u w ≤ nhdist_eq:G.dist u w = n + 1p:G.Walk u whp:p.length = G.dist u whlen:p.length = n + 1this:G.Adj (p.getVert n) w⊢ G.Adj (p.getVert n) w at this
theorem dist_eq_computable (G : SimpleGraph α) [DecidableRel G.Adj] (u v : α) :
G.dist u v = computable_dist G u v := by α:Type u_1inst✝²:Fintype αinst✝¹:DecidableEq αG:SimpleGraph αinst✝:DecidableRel G.Adju:αv:α⊢ G.dist u v = G.computable_dist u v
unfold computable_dist α:Type u_1inst✝²:Fintype αinst✝¹:DecidableEq αG:SimpleGraph αinst✝:DecidableRel G.Adju:αv:α⊢ G.dist u v = if u = v then 0 else G.bfs_dist_aux v (Fintype.card α) 1 (G.bfsStep {u})
split_ifs with h pos α:Type u_1inst✝²:Fintype αinst✝¹:DecidableEq αG:SimpleGraph αinst✝:DecidableRel G.Adju:αv:αh:u = v⊢ G.dist u v = 0neg α:Type u_1inst✝²:Fintype αinst✝¹:DecidableEq αG:SimpleGraph αinst✝:DecidableRel G.Adju:αv:αh:¬u = v⊢ G.dist u v = G.bfs_dist_aux v (Fintype.card α) 1 (G.bfsStep {u})
· pos α:Type u_1inst✝²:Fintype αinst✝¹:DecidableEq αG:SimpleGraph αinst✝:DecidableRel G.Adju:αv:αh:u = v⊢ G.dist u v = 0 subst h pos α:Type u_1inst✝²:Fintype αinst✝¹:DecidableEq αG:SimpleGraph αinst✝:DecidableRel G.Adju:α⊢ G.dist u u = 0; simp [dist_self] All goals completed! 🐙
· neg α:Type u_1inst✝²:Fintype αinst✝¹:DecidableEq αG:SimpleGraph αinst✝:DecidableRel G.Adju:αv:αh:¬u = v⊢ G.dist u v = G.bfs_dist_aux v (Fintype.card α) 1 (G.bfsStep {u}) symm neg α:Type u_1inst✝²:Fintype αinst✝¹:DecidableEq αG:SimpleGraph αinst✝:DecidableRel G.Adju:αv:αh:¬u = v⊢ G.bfs_dist_aux v (Fintype.card α) 1 (G.bfsStep {u}) = G.dist u v
suffices hsuff : ∀ (fuel depth : ℕ) (reached : Finset α),
(∀ w, w ∈ reached ↔ w ∈ G.bfsStep^[depth] {u}) →
(∀ d, d < depth → v ∉ G.bfsStep^[d] {u}) →
fuel + depth ≥ Fintype.card α + 1 →
G.bfs_dist_aux v fuel depth reached = G.dist u v by α:Type u_1inst✝²:Fintype αinst✝¹:DecidableEq αG:SimpleGraph αinst✝:DecidableRel G.Adju:αv:αh:¬u = vhsuff:∀ (fuel depth : ℕ) (reached : Finset α),
(∀ (w : α), w ∈ reached ↔ w ∈ G.bfsStep^[depth] {u}) →
(∀ d < depth, v ∉ G.bfsStep^[d] {u}) →
fuel + depth ≥ Fintype.card α + 1 → G.bfs_dist_aux v fuel depth reached = G.dist u v⊢ G.bfs_dist_aux v (Fintype.card α) 1 (G.bfsStep {u}) = G.dist u v neg α:Type u_1inst✝²:Fintype αinst✝¹:DecidableEq αG:SimpleGraph αinst✝:DecidableRel G.Adju:αv:αh:¬u = v⊢ ∀ (fuel depth : ℕ) (reached : Finset α),
(∀ (w : α), w ∈ reached ↔ w ∈ G.bfsStep^[depth] {u}) →
(∀ d < depth, v ∉ G.bfsStep^[d] {u}) →
fuel + depth ≥ Fintype.card α + 1 → G.bfs_dist_aux v fuel depth reached = G.dist u v
exact hsuff (Fintype.card α) 1 (G.bfsStep {u})
(fun w => by α:Type u_1inst✝²:Fintype αinst✝¹:DecidableEq αG:SimpleGraph αinst✝:DecidableRel G.Adju:αv:αh:¬u = vhsuff:∀ (fuel depth : ℕ) (reached : Finset α),
(∀ (w : α), w ∈ reached ↔ w ∈ G.bfsStep^[depth] {u}) →
(∀ d < depth, v ∉ G.bfsStep^[d] {u}) →
fuel + depth ≥ Fintype.card α + 1 → G.bfs_dist_aux v fuel depth reached = G.dist u vw:α⊢ w ∈ G.bfsStep {u} ↔ w ∈ G.bfsStep^[1] {u} neg α:Type u_1inst✝²:Fintype αinst✝¹:DecidableEq αG:SimpleGraph αinst✝:DecidableRel G.Adju:αv:αh:¬u = v⊢ ∀ (fuel depth : ℕ) (reached : Finset α),
(∀ (w : α), w ∈ reached ↔ w ∈ G.bfsStep^[depth] {u}) →
(∀ d < depth, v ∉ G.bfsStep^[d] {u}) →
fuel + depth ≥ Fintype.card α + 1 → G.bfs_dist_aux v fuel depth reached = G.dist u v simp All goals completed! 🐙neg α:Type u_1inst✝²:Fintype αinst✝¹:DecidableEq αG:SimpleGraph αinst✝:DecidableRel G.Adju:αv:αh:¬u = v⊢ ∀ (fuel depth : ℕ) (reached : Finset α),
(∀ (w : α), w ∈ reached ↔ w ∈ G.bfsStep^[depth] {u}) →
(∀ d < depth, v ∉ G.bfsStep^[d] {u}) →
fuel + depth ≥ Fintype.card α + 1 → G.bfs_dist_aux v fuel depth reached = G.dist u v)
(fun d hd => by α:Type u_1inst✝²:Fintype αinst✝¹:DecidableEq αG:SimpleGraph αinst✝:DecidableRel G.Adju:αv:αh:¬u = vhsuff:∀ (fuel depth : ℕ) (reached : Finset α),
(∀ (w : α), w ∈ reached ↔ w ∈ G.bfsStep^[depth] {u}) →
(∀ d < depth, v ∉ G.bfsStep^[d] {u}) →
fuel + depth ≥ Fintype.card α + 1 → G.bfs_dist_aux v fuel depth reached = G.dist u vd:ℕhd:d < 1⊢ v ∉ G.bfsStep^[d] {u}neg α:Type u_1inst✝²:Fintype αinst✝¹:DecidableEq αG:SimpleGraph αinst✝:DecidableRel G.Adju:αv:αh:¬u = v⊢ ∀ (fuel depth : ℕ) (reached : Finset α),
(∀ (w : α), w ∈ reached ↔ w ∈ G.bfsStep^[depth] {u}) →
(∀ d < depth, v ∉ G.bfsStep^[d] {u}) →
fuel + depth ≥ Fintype.card α + 1 → G.bfs_dist_aux v fuel depth reached = G.dist u v
have := Nat.lt_of_lt_of_le hd (Nat.le_refl 1) α:Type u_1inst✝²:Fintype αinst✝¹:DecidableEq αG:SimpleGraph αinst✝:DecidableRel G.Adju:αv:αh:¬u = vhsuff:∀ (fuel depth : ℕ) (reached : Finset α),
(∀ (w : α), w ∈ reached ↔ w ∈ G.bfsStep^[depth] {u}) →
(∀ d < depth, v ∉ G.bfsStep^[d] {u}) →
fuel + depth ≥ Fintype.card α + 1 → G.bfs_dist_aux v fuel depth reached = G.dist u vd:ℕhd:d < 1this:d < 1⊢ v ∉ G.bfsStep^[d] {u}neg α:Type u_1inst✝²:Fintype αinst✝¹:DecidableEq αG:SimpleGraph αinst✝:DecidableRel G.Adju:αv:αh:¬u = v⊢ ∀ (fuel depth : ℕ) (reached : Finset α),
(∀ (w : α), w ∈ reached ↔ w ∈ G.bfsStep^[depth] {u}) →
(∀ d < depth, v ∉ G.bfsStep^[d] {u}) →
fuel + depth ≥ Fintype.card α + 1 → G.bfs_dist_aux v fuel depth reached = G.dist u v
interval_cases d «0» α:Type u_1inst✝²:Fintype αinst✝¹:DecidableEq αG:SimpleGraph αinst✝:DecidableRel G.Adju:αv:αh:¬u = vhsuff:∀ (fuel depth : ℕ) (reached : Finset α),
(∀ (w : α), w ∈ reached ↔ w ∈ G.bfsStep^[depth] {u}) →
(∀ d < depth, v ∉ G.bfsStep^[d] {u}) →
fuel + depth ≥ Fintype.card α + 1 → G.bfs_dist_aux v fuel depth reached = G.dist u vd:ℕhd:0 < 1this:0 < 1⊢ v ∉ G.bfsStep^[0] {u}neg α:Type u_1inst✝²:Fintype αinst✝¹:DecidableEq αG:SimpleGraph αinst✝:DecidableRel G.Adju:αv:αh:¬u = v⊢ ∀ (fuel depth : ℕ) (reached : Finset α),
(∀ (w : α), w ∈ reached ↔ w ∈ G.bfsStep^[depth] {u}) →
(∀ d < depth, v ∉ G.bfsStep^[d] {u}) →
fuel + depth ≥ Fintype.card α + 1 → G.bfs_dist_aux v fuel depth reached = G.dist u v; simp [Finset.mem_singleton] «0» α:Type u_1inst✝²:Fintype αinst✝¹:DecidableEq αG:SimpleGraph αinst✝:DecidableRel G.Adju:αv:αh:¬u = vhsuff:∀ (fuel depth : ℕ) (reached : Finset α),
(∀ (w : α), w ∈ reached ↔ w ∈ G.bfsStep^[depth] {u}) →
(∀ d < depth, v ∉ G.bfsStep^[d] {u}) →
fuel + depth ≥ Fintype.card α + 1 → G.bfs_dist_aux v fuel depth reached = G.dist u vd:ℕhd:0 < 1this:0 < 1⊢ ¬v = uneg α:Type u_1inst✝²:Fintype αinst✝¹:DecidableEq αG:SimpleGraph αinst✝:DecidableRel G.Adju:αv:αh:¬u = v⊢ ∀ (fuel depth : ℕ) (reached : Finset α),
(∀ (w : α), w ∈ reached ↔ w ∈ G.bfsStep^[depth] {u}) →
(∀ d < depth, v ∉ G.bfsStep^[d] {u}) →
fuel + depth ≥ Fintype.card α + 1 → G.bfs_dist_aux v fuel depth reached = G.dist u v; exact Ne.symm h All goals completed! 🐙neg α:Type u_1inst✝²:Fintype αinst✝¹:DecidableEq αG:SimpleGraph αinst✝:DecidableRel G.Adju:αv:αh:¬u = v⊢ ∀ (fuel depth : ℕ) (reached : Finset α),
(∀ (w : α), w ∈ reached ↔ w ∈ G.bfsStep^[depth] {u}) →
(∀ d < depth, v ∉ G.bfsStep^[d] {u}) →
fuel + depth ≥ Fintype.card α + 1 → G.bfs_dist_aux v fuel depth reached = G.dist u v)
(by α:Type u_1inst✝²:Fintype αinst✝¹:DecidableEq αG:SimpleGraph αinst✝:DecidableRel G.Adju:αv:αh:¬u = vhsuff:∀ (fuel depth : ℕ) (reached : Finset α),
(∀ (w : α), w ∈ reached ↔ w ∈ G.bfsStep^[depth] {u}) →
(∀ d < depth, v ∉ G.bfsStep^[d] {u}) →
fuel + depth ≥ Fintype.card α + 1 → G.bfs_dist_aux v fuel depth reached = G.dist u v⊢ Fintype.card α + 1 ≥ Fintype.card α + 1neg α:Type u_1inst✝²:Fintype αinst✝¹:DecidableEq αG:SimpleGraph αinst✝:DecidableRel G.Adju:αv:αh:¬u = v⊢ ∀ (fuel depth : ℕ) (reached : Finset α),
(∀ (w : α), w ∈ reached ↔ w ∈ G.bfsStep^[depth] {u}) →
(∀ d < depth, v ∉ G.bfsStep^[d] {u}) →
fuel + depth ≥ Fintype.card α + 1 → G.bfs_dist_aux v fuel depth reached = G.dist u v omega All goals completed! 🐙neg α:Type u_1inst✝²:Fintype αinst✝¹:DecidableEq αG:SimpleGraph αinst✝:DecidableRel G.Adju:αv:αh:¬u = v⊢ ∀ (fuel depth : ℕ) (reached : Finset α),
(∀ (w : α), w ∈ reached ↔ w ∈ G.bfsStep^[depth] {u}) →
(∀ d < depth, v ∉ G.bfsStep^[d] {u}) →
fuel + depth ≥ Fintype.card α + 1 → G.bfs_dist_aux v fuel depth reached = G.dist u v)neg α:Type u_1inst✝²:Fintype αinst✝¹:DecidableEq αG:SimpleGraph αinst✝:DecidableRel G.Adju:αv:αh:¬u = v⊢ ∀ (fuel depth : ℕ) (reached : Finset α),
(∀ (w : α), w ∈ reached ↔ w ∈ G.bfsStep^[depth] {u}) →
(∀ d < depth, v ∉ G.bfsStep^[d] {u}) →
fuel + depth ≥ Fintype.card α + 1 → G.bfs_dist_aux v fuel depth reached = G.dist u v
intro fuel neg α:Type u_1inst✝²:Fintype αinst✝¹:DecidableEq αG:SimpleGraph αinst✝:DecidableRel G.Adju:αv:αh:¬u = vfuel:ℕ⊢ ∀ (depth : ℕ) (reached : Finset α),
(∀ (w : α), w ∈ reached ↔ w ∈ G.bfsStep^[depth] {u}) →
(∀ d < depth, v ∉ G.bfsStep^[d] {u}) →
fuel + depth ≥ Fintype.card α + 1 → G.bfs_dist_aux v fuel depth reached = G.dist u v
induction fuel with
| zero => neg.zero α:Type u_1inst✝²:Fintype αinst✝¹:DecidableEq αG:SimpleGraph αinst✝:DecidableRel G.Adju:αv:αh:¬u = v⊢ ∀ (depth : ℕ) (reached : Finset α),
(∀ (w : α), w ∈ reached ↔ w ∈ G.bfsStep^[depth] {u}) →
(∀ d < depth, v ∉ G.bfsStep^[d] {u}) →
0 + depth ≥ Fintype.card α + 1 → G.bfs_dist_aux v 0 depth reached = G.dist u v
intro depth reached h_inv h_not_found h_fuel neg.zero α:Type u_1inst✝²:Fintype αinst✝¹:DecidableEq αG:SimpleGraph αinst✝:DecidableRel G.Adju:αv:αh:¬u = vdepth:ℕreached:Finset αh_inv:∀ (w : α), w ∈ reached ↔ w ∈ G.bfsStep^[depth] {u}h_not_found:∀ d < depth, v ∉ G.bfsStep^[d] {u}h_fuel:0 + depth ≥ Fintype.card α + 1⊢ G.bfs_dist_aux v 0 depth reached = G.dist u v
simp [bfs_dist_aux] neg.zero α:Type u_1inst✝²:Fintype αinst✝¹:DecidableEq αG:SimpleGraph αinst✝:DecidableRel G.Adju:αv:αh:¬u = vdepth:ℕreached:Finset αh_inv:∀ (w : α), w ∈ reached ↔ w ∈ G.bfsStep^[depth] {u}h_not_found:∀ d < depth, v ∉ G.bfsStep^[d] {u}h_fuel:0 + depth ≥ Fintype.card α + 1⊢ 0 = G.dist u v
symm neg.zero α:Type u_1inst✝²:Fintype αinst✝¹:DecidableEq αG:SimpleGraph αinst✝:DecidableRel G.Adju:αv:αh:¬u = vdepth:ℕreached:Finset αh_inv:∀ (w : α), w ∈ reached ↔ w ∈ G.bfsStep^[depth] {u}h_not_found:∀ d < depth, v ∉ G.bfsStep^[d] {u}h_fuel:0 + depth ≥ Fintype.card α + 1⊢ G.dist u v = 0; rw [dist_eq_zero_iff_eq_or_not_reachable neg.zero α:Type u_1inst✝²:Fintype αinst✝¹:DecidableEq αG:SimpleGraph αinst✝:DecidableRel G.Adju:αv:αh:¬u = vdepth:ℕreached:Finset αh_inv:∀ (w : α), w ∈ reached ↔ w ∈ G.bfsStep^[depth] {u}h_not_found:∀ d < depth, v ∉ G.bfsStep^[d] {u}h_fuel:0 + depth ≥ Fintype.card α + 1⊢ u = v ∨ ¬G.Reachable u v neg.zero α:Type u_1inst✝²:Fintype αinst✝¹:DecidableEq αG:SimpleGraph αinst✝:DecidableRel G.Adju:αv:αh:¬u = vdepth:ℕreached:Finset αh_inv:∀ (w : α), w ∈ reached ↔ w ∈ G.bfsStep^[depth] {u}h_not_found:∀ d < depth, v ∉ G.bfsStep^[d] {u}h_fuel:0 + depth ≥ Fintype.card α + 1⊢ u = v ∨ ¬G.Reachable u v]neg.zero α:Type u_1inst✝²:Fintype αinst✝¹:DecidableEq αG:SimpleGraph αinst✝:DecidableRel G.Adju:αv:αh:¬u = vdepth:ℕreached:Finset αh_inv:∀ (w : α), w ∈ reached ↔ w ∈ G.bfsStep^[depth] {u}h_not_found:∀ d < depth, v ∉ G.bfsStep^[d] {u}h_fuel:0 + depth ≥ Fintype.card α + 1⊢ u = v ∨ ¬G.Reachable u v
right neg.zero α:Type u_1inst✝²:Fintype αinst✝¹:DecidableEq αG:SimpleGraph αinst✝:DecidableRel G.Adju:αv:αh:¬u = vdepth:ℕreached:Finset αh_inv:∀ (w : α), w ∈ reached ↔ w ∈ G.bfsStep^[depth] {u}h_not_found:∀ d < depth, v ∉ G.bfsStep^[d] {u}h_fuel:0 + depth ≥ Fintype.card α + 1⊢ ¬G.Reachable u v; intro hr neg.zero α:Type u_1inst✝²:Fintype αinst✝¹:DecidableEq αG:SimpleGraph αinst✝:DecidableRel G.Adju:αv:αh:¬u = vdepth:ℕreached:Finset αh_inv:∀ (w : α), w ∈ reached ↔ w ∈ G.bfsStep^[depth] {u}h_not_found:∀ d < depth, v ∉ G.bfsStep^[d] {u}h_fuel:0 + depth ≥ Fintype.card α + 1hr:G.Reachable u v⊢ False
have hpos := hr.pos_dist_of_ne h neg.zero α:Type u_1inst✝²:Fintype αinst✝¹:DecidableEq αG:SimpleGraph αinst✝:DecidableRel G.Adju:αv:αh:¬u = vdepth:ℕreached:Finset αh_inv:∀ (w : α), w ∈ reached ↔ w ∈ G.bfsStep^[depth] {u}h_not_found:∀ d < depth, v ∉ G.bfsStep^[d] {u}h_fuel:0 + depth ≥ Fintype.card α + 1hr:G.Reachable u vhpos:0 < G.dist u v⊢ False
obtain ⟨p, hp_path, hp_len⟩ := hr.exists_path_of_dist neg.zero α:Type u_1inst✝²:Fintype αinst✝¹:DecidableEq αG:SimpleGraph αinst✝:DecidableRel G.Adju:αv:αh:¬u = vdepth:ℕreached:Finset αh_inv:∀ (w : α), w ∈ reached ↔ w ∈ G.bfsStep^[depth] {u}h_not_found:∀ d < depth, v ∉ G.bfsStep^[d] {u}h_fuel:0 + depth ≥ Fintype.card α + 1hr:G.Reachable u vhpos:0 < G.dist u vp:G.Walk u vhp_path:p.IsPathhp_len:p.length = G.dist u v⊢ False
have : G.dist u v < depth := by α:Type u_1inst✝²:Fintype αinst✝¹:DecidableEq αG:SimpleGraph αinst✝:DecidableRel G.Adju:αv:α⊢ G.dist u v = G.computable_dist u v neg.zero α:Type u_1inst✝²:Fintype αinst✝¹:DecidableEq αG:SimpleGraph αinst✝:DecidableRel G.Adju:αv:αh:¬u = vdepth:ℕreached:Finset αh_inv:∀ (w : α), w ∈ reached ↔ w ∈ G.bfsStep^[depth] {u}h_not_found:∀ d < depth, v ∉ G.bfsStep^[d] {u}h_fuel:0 + depth ≥ Fintype.card α + 1hr:G.Reachable u vhpos:0 < G.dist u vp:G.Walk u vhp_path:p.IsPathhp_len:p.length = G.dist u vthis:G.dist u v < depth⊢ False
calc G.dist u v = p.length := hp_len.symm
_ < Fintype.card α := hp_path.length_lt
_ < depth := by α:Type u_1inst✝²:Fintype αinst✝¹:DecidableEq αG:SimpleGraph αinst✝:DecidableRel G.Adju:αv:αh:¬u = vdepth:ℕreached:Finset αh_inv:∀ (w : α), w ∈ reached ↔ w ∈ G.bfsStep^[depth] {u}h_not_found:∀ d < depth, v ∉ G.bfsStep^[d] {u}h_fuel:0 + depth ≥ Fintype.card α + 1hr:G.Reachable u vhpos:0 < G.dist u vp:G.Walk u vhp_path:p.IsPathhp_len:p.length = G.dist u v⊢ Fintype.card α < depthneg.zero α:Type u_1inst✝²:Fintype αinst✝¹:DecidableEq αG:SimpleGraph αinst✝:DecidableRel G.Adju:αv:αh:¬u = vdepth:ℕreached:Finset αh_inv:∀ (w : α), w ∈ reached ↔ w ∈ G.bfsStep^[depth] {u}h_not_found:∀ d < depth, v ∉ G.bfsStep^[d] {u}h_fuel:0 + depth ≥ Fintype.card α + 1hr:G.Reachable u vhpos:0 < G.dist u vp:G.Walk u vhp_path:p.IsPathhp_len:p.length = G.dist u vthis:G.dist u v < depth⊢ False omeganeg.zero α:Type u_1inst✝²:Fintype αinst✝¹:DecidableEq αG:SimpleGraph αinst✝:DecidableRel G.Adju:αv:αh:¬u = vdepth:ℕreached:Finset αh_inv:∀ (w : α), w ∈ reached ↔ w ∈ G.bfsStep^[depth] {u}h_not_found:∀ d < depth, v ∉ G.bfsStep^[d] {u}h_fuel:0 + depth ≥ Fintype.card α + 1hr:G.Reachable u vhpos:0 < G.dist u vp:G.Walk u vhp_path:p.IsPathhp_len:p.length = G.dist u vthis:G.dist u v < depth⊢ Falseneg.zero α:Type u_1inst✝²:Fintype αinst✝¹:DecidableEq αG:SimpleGraph αinst✝:DecidableRel G.Adju:αv:αh:¬u = vdepth:ℕreached:Finset αh_inv:∀ (w : α), w ∈ reached ↔ w ∈ G.bfsStep^[depth] {u}h_not_found:∀ d < depth, v ∉ G.bfsStep^[d] {u}h_fuel:0 + depth ≥ Fintype.card α + 1hr:G.Reachable u vhpos:0 < G.dist u vp:G.Walk u vhp_path:p.IsPathhp_len:p.length = G.dist u vthis:G.dist u v < depth⊢ False
exact h_not_found (G.dist u v) this
(dist_le_mem_iterate_bfsStep G u v _ (le_refl _) (Or.inr hr)) All goals completed! 🐙
| succ fuel ih => neg.succ α:Type u_1inst✝²:Fintype αinst✝¹:DecidableEq αG:SimpleGraph αinst✝:DecidableRel G.Adju:αv:αh:¬u = vfuel:ℕih:∀ (depth : ℕ) (reached : Finset α),
(∀ (w : α), w ∈ reached ↔ w ∈ G.bfsStep^[depth] {u}) →
(∀ d < depth, v ∉ G.bfsStep^[d] {u}) →
fuel + depth ≥ Fintype.card α + 1 → G.bfs_dist_aux v fuel depth reached = G.dist u v⊢ ∀ (depth : ℕ) (reached : Finset α),
(∀ (w : α), w ∈ reached ↔ w ∈ G.bfsStep^[depth] {u}) →
(∀ d < depth, v ∉ G.bfsStep^[d] {u}) →
fuel + 1 + depth ≥ Fintype.card α + 1 → G.bfs_dist_aux v (fuel + 1) depth reached = G.dist u v
intro depth reached h_inv h_not_found h_fuel neg.succ α:Type u_1inst✝²:Fintype αinst✝¹:DecidableEq αG:SimpleGraph αinst✝:DecidableRel G.Adju:αv:αh:¬u = vfuel:ℕih:∀ (depth : ℕ) (reached : Finset α),
(∀ (w : α), w ∈ reached ↔ w ∈ G.bfsStep^[depth] {u}) →
(∀ d < depth, v ∉ G.bfsStep^[d] {u}) →
fuel + depth ≥ Fintype.card α + 1 → G.bfs_dist_aux v fuel depth reached = G.dist u vdepth:ℕreached:Finset αh_inv:∀ (w : α), w ∈ reached ↔ w ∈ G.bfsStep^[depth] {u}h_not_found:∀ d < depth, v ∉ G.bfsStep^[d] {u}h_fuel:fuel + 1 + depth ≥ Fintype.card α + 1⊢ G.bfs_dist_aux v (fuel + 1) depth reached = G.dist u v
simp only [bfs_dist_aux] neg.succ α:Type u_1inst✝²:Fintype αinst✝¹:DecidableEq αG:SimpleGraph αinst✝:DecidableRel G.Adju:αv:αh:¬u = vfuel:ℕih:∀ (depth : ℕ) (reached : Finset α),
(∀ (w : α), w ∈ reached ↔ w ∈ G.bfsStep^[depth] {u}) →
(∀ d < depth, v ∉ G.bfsStep^[d] {u}) →
fuel + depth ≥ Fintype.card α + 1 → G.bfs_dist_aux v fuel depth reached = G.dist u vdepth:ℕreached:Finset αh_inv:∀ (w : α), w ∈ reached ↔ w ∈ G.bfsStep^[depth] {u}h_not_found:∀ d < depth, v ∉ G.bfsStep^[d] {u}h_fuel:fuel + 1 + depth ≥ Fintype.card α + 1⊢ (if v ∈ reached then depth else G.bfs_dist_aux v fuel (depth + 1) (G.bfsStep reached)) = G.dist u v
split_ifs with hv pos α:Type u_1inst✝²:Fintype αinst✝¹:DecidableEq αG:SimpleGraph αinst✝:DecidableRel G.Adju:αv:αh:¬u = vfuel:ℕih:∀ (depth : ℕ) (reached : Finset α),
(∀ (w : α), w ∈ reached ↔ w ∈ G.bfsStep^[depth] {u}) →
(∀ d < depth, v ∉ G.bfsStep^[d] {u}) →
fuel + depth ≥ Fintype.card α + 1 → G.bfs_dist_aux v fuel depth reached = G.dist u vdepth:ℕreached:Finset αh_inv:∀ (w : α), w ∈ reached ↔ w ∈ G.bfsStep^[depth] {u}h_not_found:∀ d < depth, v ∉ G.bfsStep^[d] {u}h_fuel:fuel + 1 + depth ≥ Fintype.card α + 1hv:v ∈ reached⊢ depth = G.dist u vneg α:Type u_1inst✝²:Fintype αinst✝¹:DecidableEq αG:SimpleGraph αinst✝:DecidableRel G.Adju:αv:αh:¬u = vfuel:ℕih:∀ (depth : ℕ) (reached : Finset α),
(∀ (w : α), w ∈ reached ↔ w ∈ G.bfsStep^[depth] {u}) →
(∀ d < depth, v ∉ G.bfsStep^[d] {u}) →
fuel + depth ≥ Fintype.card α + 1 → G.bfs_dist_aux v fuel depth reached = G.dist u vdepth:ℕreached:Finset αh_inv:∀ (w : α), w ∈ reached ↔ w ∈ G.bfsStep^[depth] {u}h_not_found:∀ d < depth, v ∉ G.bfsStep^[d] {u}h_fuel:fuel + 1 + depth ≥ Fintype.card α + 1hv:v ∉ reached⊢ G.bfs_dist_aux v fuel (depth + 1) (G.bfsStep reached) = G.dist u v
· pos α:Type u_1inst✝²:Fintype αinst✝¹:DecidableEq αG:SimpleGraph αinst✝:DecidableRel G.Adju:αv:αh:¬u = vfuel:ℕih:∀ (depth : ℕ) (reached : Finset α),
(∀ (w : α), w ∈ reached ↔ w ∈ G.bfsStep^[depth] {u}) →
(∀ d < depth, v ∉ G.bfsStep^[d] {u}) →
fuel + depth ≥ Fintype.card α + 1 → G.bfs_dist_aux v fuel depth reached = G.dist u vdepth:ℕreached:Finset αh_inv:∀ (w : α), w ∈ reached ↔ w ∈ G.bfsStep^[depth] {u}h_not_found:∀ d < depth, v ∉ G.bfsStep^[d] {u}h_fuel:fuel + 1 + depth ≥ Fintype.card α + 1hv:v ∈ reached⊢ depth = G.dist u v -- v ∈ reached = iterate^depth {u}. Show depth = dist u v.
have hle := mem_iterate_bfsStep_dist_le G u v depth ((h_inv v).mp hv) pos α:Type u_1inst✝²:Fintype αinst✝¹:DecidableEq αG:SimpleGraph αinst✝:DecidableRel G.Adju:αv:αh:¬u = vfuel:ℕih:∀ (depth : ℕ) (reached : Finset α),
(∀ (w : α), w ∈ reached ↔ w ∈ G.bfsStep^[depth] {u}) →
(∀ d < depth, v ∉ G.bfsStep^[d] {u}) →
fuel + depth ≥ Fintype.card α + 1 → G.bfs_dist_aux v fuel depth reached = G.dist u vdepth:ℕreached:Finset αh_inv:∀ (w : α), w ∈ reached ↔ w ∈ G.bfsStep^[depth] {u}h_not_found:∀ d < depth, v ∉ G.bfsStep^[d] {u}h_fuel:fuel + 1 + depth ≥ Fintype.card α + 1hv:v ∈ reachedhle:G.dist u v ≤ depth⊢ depth = G.dist u v
-- dist u v ≥ depth: if dist < depth, v ∈ iterate^(dist u v), contradicts h_not_found
by_contra hne pos α:Type u_1inst✝²:Fintype αinst✝¹:DecidableEq αG:SimpleGraph αinst✝:DecidableRel G.Adju:αv:αh:¬u = vfuel:ℕih:∀ (depth : ℕ) (reached : Finset α),
(∀ (w : α), w ∈ reached ↔ w ∈ G.bfsStep^[depth] {u}) →
(∀ d < depth, v ∉ G.bfsStep^[d] {u}) →
fuel + depth ≥ Fintype.card α + 1 → G.bfs_dist_aux v fuel depth reached = G.dist u vdepth:ℕreached:Finset αh_inv:∀ (w : α), w ∈ reached ↔ w ∈ G.bfsStep^[depth] {u}h_not_found:∀ d < depth, v ∉ G.bfsStep^[d] {u}h_fuel:fuel + 1 + depth ≥ Fintype.card α + 1hv:v ∈ reachedhle:G.dist u v ≤ depthhne:¬depth = G.dist u v⊢ False
have hlt : G.dist u v < depth := by α:Type u_1inst✝²:Fintype αinst✝¹:DecidableEq αG:SimpleGraph αinst✝:DecidableRel G.Adju:αv:α⊢ G.dist u v = G.computable_dist u v pos α:Type u_1inst✝²:Fintype αinst✝¹:DecidableEq αG:SimpleGraph αinst✝:DecidableRel G.Adju:αv:αh:¬u = vfuel:ℕih:∀ (depth : ℕ) (reached : Finset α),
(∀ (w : α), w ∈ reached ↔ w ∈ G.bfsStep^[depth] {u}) →
(∀ d < depth, v ∉ G.bfsStep^[d] {u}) →
fuel + depth ≥ Fintype.card α + 1 → G.bfs_dist_aux v fuel depth reached = G.dist u vdepth:ℕreached:Finset αh_inv:∀ (w : α), w ∈ reached ↔ w ∈ G.bfsStep^[depth] {u}h_not_found:∀ d < depth, v ∉ G.bfsStep^[d] {u}h_fuel:fuel + 1 + depth ≥ Fintype.card α + 1hv:v ∈ reachedhle:G.dist u v ≤ depthhne:¬depth = G.dist u vhlt:G.dist u v < depth⊢ False omegapos α:Type u_1inst✝²:Fintype αinst✝¹:DecidableEq αG:SimpleGraph αinst✝:DecidableRel G.Adju:αv:αh:¬u = vfuel:ℕih:∀ (depth : ℕ) (reached : Finset α),
(∀ (w : α), w ∈ reached ↔ w ∈ G.bfsStep^[depth] {u}) →
(∀ d < depth, v ∉ G.bfsStep^[d] {u}) →
fuel + depth ≥ Fintype.card α + 1 → G.bfs_dist_aux v fuel depth reached = G.dist u vdepth:ℕreached:Finset αh_inv:∀ (w : α), w ∈ reached ↔ w ∈ G.bfsStep^[depth] {u}h_not_found:∀ d < depth, v ∉ G.bfsStep^[d] {u}h_fuel:fuel + 1 + depth ≥ Fintype.card α + 1hv:v ∈ reachedhle:G.dist u v ≤ depthhne:¬depth = G.dist u vhlt:G.dist u v < depth⊢ Falsepos α:Type u_1inst✝²:Fintype αinst✝¹:DecidableEq αG:SimpleGraph αinst✝:DecidableRel G.Adju:αv:αh:¬u = vfuel:ℕih:∀ (depth : ℕ) (reached : Finset α),
(∀ (w : α), w ∈ reached ↔ w ∈ G.bfsStep^[depth] {u}) →
(∀ d < depth, v ∉ G.bfsStep^[d] {u}) →
fuel + depth ≥ Fintype.card α + 1 → G.bfs_dist_aux v fuel depth reached = G.dist u vdepth:ℕreached:Finset αh_inv:∀ (w : α), w ∈ reached ↔ w ∈ G.bfsStep^[depth] {u}h_not_found:∀ d < depth, v ∉ G.bfsStep^[d] {u}h_fuel:fuel + 1 + depth ≥ Fintype.card α + 1hv:v ∈ reachedhle:G.dist u v ≤ depthhne:¬depth = G.dist u vhlt:G.dist u v < depth⊢ False
have hreach : G.Reachable u v := G.reachable_of_mem_iterate_bfsStep ((h_inv v).mp hv) pos α:Type u_1inst✝²:Fintype αinst✝¹:DecidableEq αG:SimpleGraph αinst✝:DecidableRel G.Adju:αv:αh:¬u = vfuel:ℕih:∀ (depth : ℕ) (reached : Finset α),
(∀ (w : α), w ∈ reached ↔ w ∈ G.bfsStep^[depth] {u}) →
(∀ d < depth, v ∉ G.bfsStep^[d] {u}) →
fuel + depth ≥ Fintype.card α + 1 → G.bfs_dist_aux v fuel depth reached = G.dist u vdepth:ℕreached:Finset αh_inv:∀ (w : α), w ∈ reached ↔ w ∈ G.bfsStep^[depth] {u}h_not_found:∀ d < depth, v ∉ G.bfsStep^[d] {u}h_fuel:fuel + 1 + depth ≥ Fintype.card α + 1hv:v ∈ reachedhle:G.dist u v ≤ depthhne:¬depth = G.dist u vhlt:G.dist u v < depthhreach:G.Reachable u v⊢ False
exact h_not_found (G.dist u v) hlt
(dist_le_mem_iterate_bfsStep G u v _ le_rfl (Or.inr hreach)) All goals completed! 🐙
· neg α:Type u_1inst✝²:Fintype αinst✝¹:DecidableEq αG:SimpleGraph αinst✝:DecidableRel G.Adju:αv:αh:¬u = vfuel:ℕih:∀ (depth : ℕ) (reached : Finset α),
(∀ (w : α), w ∈ reached ↔ w ∈ G.bfsStep^[depth] {u}) →
(∀ d < depth, v ∉ G.bfsStep^[d] {u}) →
fuel + depth ≥ Fintype.card α + 1 → G.bfs_dist_aux v fuel depth reached = G.dist u vdepth:ℕreached:Finset αh_inv:∀ (w : α), w ∈ reached ↔ w ∈ G.bfsStep^[depth] {u}h_not_found:∀ d < depth, v ∉ G.bfsStep^[d] {u}h_fuel:fuel + 1 + depth ≥ Fintype.card α + 1hv:v ∉ reached⊢ G.bfs_dist_aux v fuel (depth + 1) (G.bfsStep reached) = G.dist u v -- v ∉ reached. Recurse.
have h_inv' : ∀ w, w ∈ G.bfsStep reached ↔
w ∈ G.bfsStep^[depth + 1] {u} := by α:Type u_1inst✝²:Fintype αinst✝¹:DecidableEq αG:SimpleGraph αinst✝:DecidableRel G.Adju:αv:α⊢ G.dist u v = G.computable_dist u v neg α:Type u_1inst✝²:Fintype αinst✝¹:DecidableEq αG:SimpleGraph αinst✝:DecidableRel G.Adju:αv:αh:¬u = vfuel:ℕih:∀ (depth : ℕ) (reached : Finset α),
(∀ (w : α), w ∈ reached ↔ w ∈ G.bfsStep^[depth] {u}) →
(∀ d < depth, v ∉ G.bfsStep^[d] {u}) →
fuel + depth ≥ Fintype.card α + 1 → G.bfs_dist_aux v fuel depth reached = G.dist u vdepth:ℕreached:Finset αh_inv:∀ (w : α), w ∈ reached ↔ w ∈ G.bfsStep^[depth] {u}h_not_found:∀ d < depth, v ∉ G.bfsStep^[d] {u}h_fuel:fuel + 1 + depth ≥ Fintype.card α + 1hv:v ∉ reachedh_inv':∀ (w : α), w ∈ G.bfsStep reached ↔ w ∈ G.bfsStep^[depth + 1] {u}⊢ G.bfs_dist_aux v fuel (depth + 1) (G.bfsStep reached) = G.dist u v
intro w α:Type u_1inst✝²:Fintype αinst✝¹:DecidableEq αG:SimpleGraph αinst✝:DecidableRel G.Adju:αv:αh:¬u = vfuel:ℕih:∀ (depth : ℕ) (reached : Finset α),
(∀ (w : α), w ∈ reached ↔ w ∈ G.bfsStep^[depth] {u}) →
(∀ d < depth, v ∉ G.bfsStep^[d] {u}) →
fuel + depth ≥ Fintype.card α + 1 → G.bfs_dist_aux v fuel depth reached = G.dist u vdepth:ℕreached:Finset αh_inv:∀ (w : α), w ∈ reached ↔ w ∈ G.bfsStep^[depth] {u}h_not_found:∀ d < depth, v ∉ G.bfsStep^[d] {u}h_fuel:fuel + 1 + depth ≥ Fintype.card α + 1hv:v ∉ reachedw:α⊢ w ∈ G.bfsStep reached ↔ w ∈ G.bfsStep^[depth + 1] {u}neg α:Type u_1inst✝²:Fintype αinst✝¹:DecidableEq αG:SimpleGraph αinst✝:DecidableRel G.Adju:αv:αh:¬u = vfuel:ℕih:∀ (depth : ℕ) (reached : Finset α),
(∀ (w : α), w ∈ reached ↔ w ∈ G.bfsStep^[depth] {u}) →
(∀ d < depth, v ∉ G.bfsStep^[d] {u}) →
fuel + depth ≥ Fintype.card α + 1 → G.bfs_dist_aux v fuel depth reached = G.dist u vdepth:ℕreached:Finset αh_inv:∀ (w : α), w ∈ reached ↔ w ∈ G.bfsStep^[depth] {u}h_not_found:∀ d < depth, v ∉ G.bfsStep^[d] {u}h_fuel:fuel + 1 + depth ≥ Fintype.card α + 1hv:v ∉ reachedh_inv':∀ (w : α), w ∈ G.bfsStep reached ↔ w ∈ G.bfsStep^[depth + 1] {u}⊢ G.bfs_dist_aux v fuel (depth + 1) (G.bfsStep reached) = G.dist u v
have heq : G.bfsStep reached = G.bfsStep (G.bfsStep^[depth] {u}) := by α:Type u_1inst✝²:Fintype αinst✝¹:DecidableEq αG:SimpleGraph αinst✝:DecidableRel G.Adju:αv:α⊢ G.dist u v = G.computable_dist u v α:Type u_1inst✝²:Fintype αinst✝¹:DecidableEq αG:SimpleGraph αinst✝:DecidableRel G.Adju:αv:αh:¬u = vfuel:ℕih:∀ (depth : ℕ) (reached : Finset α),
(∀ (w : α), w ∈ reached ↔ w ∈ G.bfsStep^[depth] {u}) →
(∀ d < depth, v ∉ G.bfsStep^[d] {u}) →
fuel + depth ≥ Fintype.card α + 1 → G.bfs_dist_aux v fuel depth reached = G.dist u vdepth:ℕreached:Finset αh_inv:∀ (w : α), w ∈ reached ↔ w ∈ G.bfsStep^[depth] {u}h_not_found:∀ d < depth, v ∉ G.bfsStep^[d] {u}h_fuel:fuel + 1 + depth ≥ Fintype.card α + 1hv:v ∉ reachedw:αheq:G.bfsStep reached = G.bfsStep (G.bfsStep^[depth] {u})⊢ w ∈ G.bfsStep reached ↔ w ∈ G.bfsStep^[depth + 1] {u}neg α:Type u_1inst✝²:Fintype αinst✝¹:DecidableEq αG:SimpleGraph αinst✝:DecidableRel G.Adju:αv:αh:¬u = vfuel:ℕih:∀ (depth : ℕ) (reached : Finset α),
(∀ (w : α), w ∈ reached ↔ w ∈ G.bfsStep^[depth] {u}) →
(∀ d < depth, v ∉ G.bfsStep^[d] {u}) →
fuel + depth ≥ Fintype.card α + 1 → G.bfs_dist_aux v fuel depth reached = G.dist u vdepth:ℕreached:Finset αh_inv:∀ (w : α), w ∈ reached ↔ w ∈ G.bfsStep^[depth] {u}h_not_found:∀ d < depth, v ∉ G.bfsStep^[d] {u}h_fuel:fuel + 1 + depth ≥ Fintype.card α + 1hv:v ∉ reachedh_inv':∀ (w : α), w ∈ G.bfsStep reached ↔ w ∈ G.bfsStep^[depth + 1] {u}⊢ G.bfs_dist_aux v fuel (depth + 1) (G.bfsStep reached) = G.dist u v
ext x α:Type u_1inst✝²:Fintype αinst✝¹:DecidableEq αG:SimpleGraph αinst✝:DecidableRel G.Adju:αv:αh:¬u = vfuel:ℕih:∀ (depth : ℕ) (reached : Finset α),
(∀ (w : α), w ∈ reached ↔ w ∈ G.bfsStep^[depth] {u}) →
(∀ d < depth, v ∉ G.bfsStep^[d] {u}) →
fuel + depth ≥ Fintype.card α + 1 → G.bfs_dist_aux v fuel depth reached = G.dist u vdepth:ℕreached:Finset αh_inv:∀ (w : α), w ∈ reached ↔ w ∈ G.bfsStep^[depth] {u}h_not_found:∀ d < depth, v ∉ G.bfsStep^[d] {u}h_fuel:fuel + 1 + depth ≥ Fintype.card α + 1hv:v ∉ reachedw:αx:α⊢ x ∈ G.bfsStep reached ↔ x ∈ G.bfsStep (G.bfsStep^[depth] {u}) α:Type u_1inst✝²:Fintype αinst✝¹:DecidableEq αG:SimpleGraph αinst✝:DecidableRel G.Adju:αv:αh:¬u = vfuel:ℕih:∀ (depth : ℕ) (reached : Finset α),
(∀ (w : α), w ∈ reached ↔ w ∈ G.bfsStep^[depth] {u}) →
(∀ d < depth, v ∉ G.bfsStep^[d] {u}) →
fuel + depth ≥ Fintype.card α + 1 → G.bfs_dist_aux v fuel depth reached = G.dist u vdepth:ℕreached:Finset αh_inv:∀ (w : α), w ∈ reached ↔ w ∈ G.bfsStep^[depth] {u}h_not_found:∀ d < depth, v ∉ G.bfsStep^[d] {u}h_fuel:fuel + 1 + depth ≥ Fintype.card α + 1hv:v ∉ reachedw:αheq:G.bfsStep reached = G.bfsStep (G.bfsStep^[depth] {u})⊢ w ∈ G.bfsStep reached ↔ w ∈ G.bfsStep^[depth + 1] {u}neg α:Type u_1inst✝²:Fintype αinst✝¹:DecidableEq αG:SimpleGraph αinst✝:DecidableRel G.Adju:αv:αh:¬u = vfuel:ℕih:∀ (depth : ℕ) (reached : Finset α),
(∀ (w : α), w ∈ reached ↔ w ∈ G.bfsStep^[depth] {u}) →
(∀ d < depth, v ∉ G.bfsStep^[d] {u}) →
fuel + depth ≥ Fintype.card α + 1 → G.bfs_dist_aux v fuel depth reached = G.dist u vdepth:ℕreached:Finset αh_inv:∀ (w : α), w ∈ reached ↔ w ∈ G.bfsStep^[depth] {u}h_not_found:∀ d < depth, v ∉ G.bfsStep^[d] {u}h_fuel:fuel + 1 + depth ≥ Fintype.card α + 1hv:v ∉ reachedh_inv':∀ (w : α), w ∈ G.bfsStep reached ↔ w ∈ G.bfsStep^[depth + 1] {u}⊢ G.bfs_dist_aux v fuel (depth + 1) (G.bfsStep reached) = G.dist u v; simp only [mem_bfsStep, h_inv] α:Type u_1inst✝²:Fintype αinst✝¹:DecidableEq αG:SimpleGraph αinst✝:DecidableRel G.Adju:αv:αh:¬u = vfuel:ℕih:∀ (depth : ℕ) (reached : Finset α),
(∀ (w : α), w ∈ reached ↔ w ∈ G.bfsStep^[depth] {u}) →
(∀ d < depth, v ∉ G.bfsStep^[d] {u}) →
fuel + depth ≥ Fintype.card α + 1 → G.bfs_dist_aux v fuel depth reached = G.dist u vdepth:ℕreached:Finset αh_inv:∀ (w : α), w ∈ reached ↔ w ∈ G.bfsStep^[depth] {u}h_not_found:∀ d < depth, v ∉ G.bfsStep^[d] {u}h_fuel:fuel + 1 + depth ≥ Fintype.card α + 1hv:v ∉ reachedw:αheq:G.bfsStep reached = G.bfsStep (G.bfsStep^[depth] {u})⊢ w ∈ G.bfsStep reached ↔ w ∈ G.bfsStep^[depth + 1] {u}neg α:Type u_1inst✝²:Fintype αinst✝¹:DecidableEq αG:SimpleGraph αinst✝:DecidableRel G.Adju:αv:αh:¬u = vfuel:ℕih:∀ (depth : ℕ) (reached : Finset α),
(∀ (w : α), w ∈ reached ↔ w ∈ G.bfsStep^[depth] {u}) →
(∀ d < depth, v ∉ G.bfsStep^[d] {u}) →
fuel + depth ≥ Fintype.card α + 1 → G.bfs_dist_aux v fuel depth reached = G.dist u vdepth:ℕreached:Finset αh_inv:∀ (w : α), w ∈ reached ↔ w ∈ G.bfsStep^[depth] {u}h_not_found:∀ d < depth, v ∉ G.bfsStep^[d] {u}h_fuel:fuel + 1 + depth ≥ Fintype.card α + 1hv:v ∉ reachedh_inv':∀ (w : α), w ∈ G.bfsStep reached ↔ w ∈ G.bfsStep^[depth + 1] {u}⊢ G.bfs_dist_aux v fuel (depth + 1) (G.bfsStep reached) = G.dist u v α:Type u_1inst✝²:Fintype αinst✝¹:DecidableEq αG:SimpleGraph αinst✝:DecidableRel G.Adju:αv:αh:¬u = vfuel:ℕih:∀ (depth : ℕ) (reached : Finset α),
(∀ (w : α), w ∈ reached ↔ w ∈ G.bfsStep^[depth] {u}) →
(∀ d < depth, v ∉ G.bfsStep^[d] {u}) →
fuel + depth ≥ Fintype.card α + 1 → G.bfs_dist_aux v fuel depth reached = G.dist u vdepth:ℕreached:Finset αh_inv:∀ (w : α), w ∈ reached ↔ w ∈ G.bfsStep^[depth] {u}h_not_found:∀ d < depth, v ∉ G.bfsStep^[d] {u}h_fuel:fuel + 1 + depth ≥ Fintype.card α + 1hv:v ∉ reachedw:αheq:G.bfsStep reached = G.bfsStep (G.bfsStep^[depth] {u})⊢ w ∈ G.bfsStep reached ↔ w ∈ G.bfsStep^[depth + 1] {u}neg α:Type u_1inst✝²:Fintype αinst✝¹:DecidableEq αG:SimpleGraph αinst✝:DecidableRel G.Adju:αv:αh:¬u = vfuel:ℕih:∀ (depth : ℕ) (reached : Finset α),
(∀ (w : α), w ∈ reached ↔ w ∈ G.bfsStep^[depth] {u}) →
(∀ d < depth, v ∉ G.bfsStep^[d] {u}) →
fuel + depth ≥ Fintype.card α + 1 → G.bfs_dist_aux v fuel depth reached = G.dist u vdepth:ℕreached:Finset αh_inv:∀ (w : α), w ∈ reached ↔ w ∈ G.bfsStep^[depth] {u}h_not_found:∀ d < depth, v ∉ G.bfsStep^[d] {u}h_fuel:fuel + 1 + depth ≥ Fintype.card α + 1hv:v ∉ reachedh_inv':∀ (w : α), w ∈ G.bfsStep reached ↔ w ∈ G.bfsStep^[depth + 1] {u}⊢ G.bfs_dist_aux v fuel (depth + 1) (G.bfsStep reached) = G.dist u v
rw [heq, α:Type u_1inst✝²:Fintype αinst✝¹:DecidableEq αG:SimpleGraph αinst✝:DecidableRel G.Adju:αv:αh:¬u = vfuel:ℕih:∀ (depth : ℕ) (reached : Finset α),
(∀ (w : α), w ∈ reached ↔ w ∈ G.bfsStep^[depth] {u}) →
(∀ d < depth, v ∉ G.bfsStep^[d] {u}) →
fuel + depth ≥ Fintype.card α + 1 → G.bfs_dist_aux v fuel depth reached = G.dist u vdepth:ℕreached:Finset αh_inv:∀ (w : α), w ∈ reached ↔ w ∈ G.bfsStep^[depth] {u}h_not_found:∀ d < depth, v ∉ G.bfsStep^[d] {u}h_fuel:fuel + 1 + depth ≥ Fintype.card α + 1hv:v ∉ reachedw:αheq:G.bfsStep reached = G.bfsStep (G.bfsStep^[depth] {u})⊢ w ∈ G.bfsStep (G.bfsStep^[depth] {u}) ↔ w ∈ G.bfsStep^[depth + 1] {u}neg α:Type u_1inst✝²:Fintype αinst✝¹:DecidableEq αG:SimpleGraph αinst✝:DecidableRel G.Adju:αv:αh:¬u = vfuel:ℕih:∀ (depth : ℕ) (reached : Finset α),
(∀ (w : α), w ∈ reached ↔ w ∈ G.bfsStep^[depth] {u}) →
(∀ d < depth, v ∉ G.bfsStep^[d] {u}) →
fuel + depth ≥ Fintype.card α + 1 → G.bfs_dist_aux v fuel depth reached = G.dist u vdepth:ℕreached:Finset αh_inv:∀ (w : α), w ∈ reached ↔ w ∈ G.bfsStep^[depth] {u}h_not_found:∀ d < depth, v ∉ G.bfsStep^[d] {u}h_fuel:fuel + 1 + depth ≥ Fintype.card α + 1hv:v ∉ reachedh_inv':∀ (w : α), w ∈ G.bfsStep reached ↔ w ∈ G.bfsStep^[depth + 1] {u}⊢ G.bfs_dist_aux v fuel (depth + 1) (G.bfsStep reached) = G.dist u v Function.iterate_succ', α:Type u_1inst✝²:Fintype αinst✝¹:DecidableEq αG:SimpleGraph αinst✝:DecidableRel G.Adju:αv:αh:¬u = vfuel:ℕih:∀ (depth : ℕ) (reached : Finset α),
(∀ (w : α), w ∈ reached ↔ w ∈ G.bfsStep^[depth] {u}) →
(∀ d < depth, v ∉ G.bfsStep^[d] {u}) →
fuel + depth ≥ Fintype.card α + 1 → G.bfs_dist_aux v fuel depth reached = G.dist u vdepth:ℕreached:Finset αh_inv:∀ (w : α), w ∈ reached ↔ w ∈ G.bfsStep^[depth] {u}h_not_found:∀ d < depth, v ∉ G.bfsStep^[d] {u}h_fuel:fuel + 1 + depth ≥ Fintype.card α + 1hv:v ∉ reachedw:αheq:G.bfsStep reached = G.bfsStep (G.bfsStep^[depth] {u})⊢ w ∈ G.bfsStep (G.bfsStep^[depth] {u}) ↔ w ∈ (G.bfsStep ∘ G.bfsStep^[depth]) {u}neg α:Type u_1inst✝²:Fintype αinst✝¹:DecidableEq αG:SimpleGraph αinst✝:DecidableRel G.Adju:αv:αh:¬u = vfuel:ℕih:∀ (depth : ℕ) (reached : Finset α),
(∀ (w : α), w ∈ reached ↔ w ∈ G.bfsStep^[depth] {u}) →
(∀ d < depth, v ∉ G.bfsStep^[d] {u}) →
fuel + depth ≥ Fintype.card α + 1 → G.bfs_dist_aux v fuel depth reached = G.dist u vdepth:ℕreached:Finset αh_inv:∀ (w : α), w ∈ reached ↔ w ∈ G.bfsStep^[depth] {u}h_not_found:∀ d < depth, v ∉ G.bfsStep^[d] {u}h_fuel:fuel + 1 + depth ≥ Fintype.card α + 1hv:v ∉ reachedh_inv':∀ (w : α), w ∈ G.bfsStep reached ↔ w ∈ G.bfsStep^[depth + 1] {u}⊢ G.bfs_dist_aux v fuel (depth + 1) (G.bfsStep reached) = G.dist u v Function.comp α:Type u_1inst✝²:Fintype αinst✝¹:DecidableEq αG:SimpleGraph αinst✝:DecidableRel G.Adju:αv:αh:¬u = vfuel:ℕih:∀ (depth : ℕ) (reached : Finset α),
(∀ (w : α), w ∈ reached ↔ w ∈ G.bfsStep^[depth] {u}) →
(∀ d < depth, v ∉ G.bfsStep^[d] {u}) →
fuel + depth ≥ Fintype.card α + 1 → G.bfs_dist_aux v fuel depth reached = G.dist u vdepth:ℕreached:Finset αh_inv:∀ (w : α), w ∈ reached ↔ w ∈ G.bfsStep^[depth] {u}h_not_found:∀ d < depth, v ∉ G.bfsStep^[d] {u}h_fuel:fuel + 1 + depth ≥ Fintype.card α + 1hv:v ∉ reachedw:αheq:G.bfsStep reached = G.bfsStep (G.bfsStep^[depth] {u})⊢ w ∈ G.bfsStep (G.bfsStep^[depth] {u}) ↔ w ∈ G.bfsStep (G.bfsStep^[depth] {u})neg α:Type u_1inst✝²:Fintype αinst✝¹:DecidableEq αG:SimpleGraph αinst✝:DecidableRel G.Adju:αv:αh:¬u = vfuel:ℕih:∀ (depth : ℕ) (reached : Finset α),
(∀ (w : α), w ∈ reached ↔ w ∈ G.bfsStep^[depth] {u}) →
(∀ d < depth, v ∉ G.bfsStep^[d] {u}) →
fuel + depth ≥ Fintype.card α + 1 → G.bfs_dist_aux v fuel depth reached = G.dist u vdepth:ℕreached:Finset αh_inv:∀ (w : α), w ∈ reached ↔ w ∈ G.bfsStep^[depth] {u}h_not_found:∀ d < depth, v ∉ G.bfsStep^[d] {u}h_fuel:fuel + 1 + depth ≥ Fintype.card α + 1hv:v ∉ reachedh_inv':∀ (w : α), w ∈ G.bfsStep reached ↔ w ∈ G.bfsStep^[depth + 1] {u}⊢ G.bfs_dist_aux v fuel (depth + 1) (G.bfsStep reached) = G.dist u v]neg α:Type u_1inst✝²:Fintype αinst✝¹:DecidableEq αG:SimpleGraph αinst✝:DecidableRel G.Adju:αv:αh:¬u = vfuel:ℕih:∀ (depth : ℕ) (reached : Finset α),
(∀ (w : α), w ∈ reached ↔ w ∈ G.bfsStep^[depth] {u}) →
(∀ d < depth, v ∉ G.bfsStep^[d] {u}) →
fuel + depth ≥ Fintype.card α + 1 → G.bfs_dist_aux v fuel depth reached = G.dist u vdepth:ℕreached:Finset αh_inv:∀ (w : α), w ∈ reached ↔ w ∈ G.bfsStep^[depth] {u}h_not_found:∀ d < depth, v ∉ G.bfsStep^[d] {u}h_fuel:fuel + 1 + depth ≥ Fintype.card α + 1hv:v ∉ reachedh_inv':∀ (w : α), w ∈ G.bfsStep reached ↔ w ∈ G.bfsStep^[depth + 1] {u}⊢ G.bfs_dist_aux v fuel (depth + 1) (G.bfsStep reached) = G.dist u vneg α:Type u_1inst✝²:Fintype αinst✝¹:DecidableEq αG:SimpleGraph αinst✝:DecidableRel G.Adju:αv:αh:¬u = vfuel:ℕih:∀ (depth : ℕ) (reached : Finset α),
(∀ (w : α), w ∈ reached ↔ w ∈ G.bfsStep^[depth] {u}) →
(∀ d < depth, v ∉ G.bfsStep^[d] {u}) →
fuel + depth ≥ Fintype.card α + 1 → G.bfs_dist_aux v fuel depth reached = G.dist u vdepth:ℕreached:Finset αh_inv:∀ (w : α), w ∈ reached ↔ w ∈ G.bfsStep^[depth] {u}h_not_found:∀ d < depth, v ∉ G.bfsStep^[d] {u}h_fuel:fuel + 1 + depth ≥ Fintype.card α + 1hv:v ∉ reachedh_inv':∀ (w : α), w ∈ G.bfsStep reached ↔ w ∈ G.bfsStep^[depth + 1] {u}⊢ G.bfs_dist_aux v fuel (depth + 1) (G.bfsStep reached) = G.dist u v
exact ih (depth + 1) (G.bfsStep reached) h_inv'
(fun d hd => by α:Type u_1inst✝²:Fintype αinst✝¹:DecidableEq αG:SimpleGraph αinst✝:DecidableRel G.Adju:αv:αh:¬u = vfuel:ℕih:∀ (depth : ℕ) (reached : Finset α),
(∀ (w : α), w ∈ reached ↔ w ∈ G.bfsStep^[depth] {u}) →
(∀ d < depth, v ∉ G.bfsStep^[d] {u}) →
fuel + depth ≥ Fintype.card α + 1 → G.bfs_dist_aux v fuel depth reached = G.dist u vdepth:ℕreached:Finset αh_inv:∀ (w : α), w ∈ reached ↔ w ∈ G.bfsStep^[depth] {u}h_not_found:∀ d < depth, v ∉ G.bfsStep^[d] {u}h_fuel:fuel + 1 + depth ≥ Fintype.card α + 1hv:v ∉ reachedh_inv':∀ (w : α), w ∈ G.bfsStep reached ↔ w ∈ G.bfsStep^[depth + 1] {u}d:ℕhd:d < depth + 1⊢ v ∉ G.bfsStep^[d] {u}
rcases Nat.lt_succ_iff_lt_or_eq.mp hd with hd | hd inl α:Type u_1inst✝²:Fintype αinst✝¹:DecidableEq αG:SimpleGraph αinst✝:DecidableRel G.Adju:αv:αh:¬u = vfuel:ℕih:∀ (depth : ℕ) (reached : Finset α),
(∀ (w : α), w ∈ reached ↔ w ∈ G.bfsStep^[depth] {u}) →
(∀ d < depth, v ∉ G.bfsStep^[d] {u}) →
fuel + depth ≥ Fintype.card α + 1 → G.bfs_dist_aux v fuel depth reached = G.dist u vdepth:ℕreached:Finset αh_inv:∀ (w : α), w ∈ reached ↔ w ∈ G.bfsStep^[depth] {u}h_not_found:∀ d < depth, v ∉ G.bfsStep^[d] {u}h_fuel:fuel + 1 + depth ≥ Fintype.card α + 1hv:v ∉ reachedh_inv':∀ (w : α), w ∈ G.bfsStep reached ↔ w ∈ G.bfsStep^[depth + 1] {u}d:ℕhd✝:d < depth + 1hd:d < depth⊢ v ∉ G.bfsStep^[d] {u}inr α:Type u_1inst✝²:Fintype αinst✝¹:DecidableEq αG:SimpleGraph αinst✝:DecidableRel G.Adju:αv:αh:¬u = vfuel:ℕih:∀ (depth : ℕ) (reached : Finset α),
(∀ (w : α), w ∈ reached ↔ w ∈ G.bfsStep^[depth] {u}) →
(∀ d < depth, v ∉ G.bfsStep^[d] {u}) →
fuel + depth ≥ Fintype.card α + 1 → G.bfs_dist_aux v fuel depth reached = G.dist u vdepth:ℕreached:Finset αh_inv:∀ (w : α), w ∈ reached ↔ w ∈ G.bfsStep^[depth] {u}h_not_found:∀ d < depth, v ∉ G.bfsStep^[d] {u}h_fuel:fuel + 1 + depth ≥ Fintype.card α + 1hv:v ∉ reachedh_inv':∀ (w : α), w ∈ G.bfsStep reached ↔ w ∈ G.bfsStep^[depth + 1] {u}d:ℕhd✝:d < depth + 1hd:d = depth⊢ v ∉ G.bfsStep^[d] {u}
· inl α:Type u_1inst✝²:Fintype αinst✝¹:DecidableEq αG:SimpleGraph αinst✝:DecidableRel G.Adju:αv:αh:¬u = vfuel:ℕih:∀ (depth : ℕ) (reached : Finset α),
(∀ (w : α), w ∈ reached ↔ w ∈ G.bfsStep^[depth] {u}) →
(∀ d < depth, v ∉ G.bfsStep^[d] {u}) →
fuel + depth ≥ Fintype.card α + 1 → G.bfs_dist_aux v fuel depth reached = G.dist u vdepth:ℕreached:Finset αh_inv:∀ (w : α), w ∈ reached ↔ w ∈ G.bfsStep^[depth] {u}h_not_found:∀ d < depth, v ∉ G.bfsStep^[d] {u}h_fuel:fuel + 1 + depth ≥ Fintype.card α + 1hv:v ∉ reachedh_inv':∀ (w : α), w ∈ G.bfsStep reached ↔ w ∈ G.bfsStep^[depth + 1] {u}d:ℕhd✝:d < depth + 1hd:d < depth⊢ v ∉ G.bfsStep^[d] {u} exact h_not_found d (by α:Type u_1inst✝²:Fintype αinst✝¹:DecidableEq αG:SimpleGraph αinst✝:DecidableRel G.Adju:αv:αh:¬u = vfuel:ℕih:∀ (depth : ℕ) (reached : Finset α),
(∀ (w : α), w ∈ reached ↔ w ∈ G.bfsStep^[depth] {u}) →
(∀ d < depth, v ∉ G.bfsStep^[d] {u}) →
fuel + depth ≥ Fintype.card α + 1 → G.bfs_dist_aux v fuel depth reached = G.dist u vdepth:ℕreached:Finset αh_inv:∀ (w : α), w ∈ reached ↔ w ∈ G.bfsStep^[depth] {u}h_not_found:∀ d < depth, v ∉ G.bfsStep^[d] {u}h_fuel:fuel + 1 + depth ≥ Fintype.card α + 1hv:v ∉ reachedh_inv':∀ (w : α), w ∈ G.bfsStep reached ↔ w ∈ G.bfsStep^[depth + 1] {u}d:ℕhd✝:d < depth + 1hd:d < depth⊢ d < depth omega All goals completed! 🐙)
· inr α:Type u_1inst✝²:Fintype αinst✝¹:DecidableEq αG:SimpleGraph αinst✝:DecidableRel G.Adju:αv:αh:¬u = vfuel:ℕih:∀ (depth : ℕ) (reached : Finset α),
(∀ (w : α), w ∈ reached ↔ w ∈ G.bfsStep^[depth] {u}) →
(∀ d < depth, v ∉ G.bfsStep^[d] {u}) →
fuel + depth ≥ Fintype.card α + 1 → G.bfs_dist_aux v fuel depth reached = G.dist u vdepth:ℕreached:Finset αh_inv:∀ (w : α), w ∈ reached ↔ w ∈ G.bfsStep^[depth] {u}h_not_found:∀ d < depth, v ∉ G.bfsStep^[d] {u}h_fuel:fuel + 1 + depth ≥ Fintype.card α + 1hv:v ∉ reachedh_inv':∀ (w : α), w ∈ G.bfsStep reached ↔ w ∈ G.bfsStep^[depth + 1] {u}d:ℕhd✝:d < depth + 1hd:d = depth⊢ v ∉ G.bfsStep^[d] {u} subst hd inr α:Type u_1inst✝²:Fintype αinst✝¹:DecidableEq αG:SimpleGraph αinst✝:DecidableRel G.Adju:αv:αh:¬u = vfuel:ℕih:∀ (depth : ℕ) (reached : Finset α),
(∀ (w : α), w ∈ reached ↔ w ∈ G.bfsStep^[depth] {u}) →
(∀ d < depth, v ∉ G.bfsStep^[d] {u}) →
fuel + depth ≥ Fintype.card α + 1 → G.bfs_dist_aux v fuel depth reached = G.dist u vreached:Finset αhv:v ∉ reachedd:ℕh_inv:∀ (w : α), w ∈ reached ↔ w ∈ G.bfsStep^[d] {u}h_not_found:∀ d_1 < d, v ∉ G.bfsStep^[d_1] {u}h_fuel:fuel + 1 + d ≥ Fintype.card α + 1h_inv':∀ (w : α), w ∈ G.bfsStep reached ↔ w ∈ G.bfsStep^[d + 1] {u}hd:d < d + 1⊢ v ∉ G.bfsStep^[d] {u}; rwa [h_inv inr α:Type u_1inst✝²:Fintype αinst✝¹:DecidableEq αG:SimpleGraph αinst✝:DecidableRel G.Adju:αv:αh:¬u = vfuel:ℕih:∀ (depth : ℕ) (reached : Finset α),
(∀ (w : α), w ∈ reached ↔ w ∈ G.bfsStep^[depth] {u}) →
(∀ d < depth, v ∉ G.bfsStep^[d] {u}) →
fuel + depth ≥ Fintype.card α + 1 → G.bfs_dist_aux v fuel depth reached = G.dist u vreached:Finset αd:ℕhv:v ∉ G.bfsStep^[d] {u}h_inv:∀ (w : α), w ∈ reached ↔ w ∈ G.bfsStep^[d] {u}h_not_found:∀ d_1 < d, v ∉ G.bfsStep^[d_1] {u}h_fuel:fuel + 1 + d ≥ Fintype.card α + 1h_inv':∀ (w : α), w ∈ G.bfsStep reached ↔ w ∈ G.bfsStep^[d + 1] {u}hd:d < d + 1⊢ v ∉ G.bfsStep^[d] {u}] inr α:Type u_1inst✝²:Fintype αinst✝¹:DecidableEq αG:SimpleGraph αinst✝:DecidableRel G.Adju:αv:αh:¬u = vfuel:ℕih:∀ (depth : ℕ) (reached : Finset α),
(∀ (w : α), w ∈ reached ↔ w ∈ G.bfsStep^[depth] {u}) →
(∀ d < depth, v ∉ G.bfsStep^[d] {u}) →
fuel + depth ≥ Fintype.card α + 1 → G.bfs_dist_aux v fuel depth reached = G.dist u vreached:Finset αd:ℕhv:v ∉ G.bfsStep^[d] {u}h_inv:∀ (w : α), w ∈ reached ↔ w ∈ G.bfsStep^[d] {u}h_not_found:∀ d_1 < d, v ∉ G.bfsStep^[d_1] {u}h_fuel:fuel + 1 + d ≥ Fintype.card α + 1h_inv':∀ (w : α), w ∈ G.bfsStep reached ↔ w ∈ G.bfsStep^[d + 1] {u}hd:d < d + 1⊢ v ∉ G.bfsStep^[d] {u} at hv)
(by α:Type u_1inst✝²:Fintype αinst✝¹:DecidableEq αG:SimpleGraph αinst✝:DecidableRel G.Adju:αv:αh:¬u = vfuel:ℕih:∀ (depth : ℕ) (reached : Finset α),
(∀ (w : α), w ∈ reached ↔ w ∈ G.bfsStep^[depth] {u}) →
(∀ d < depth, v ∉ G.bfsStep^[d] {u}) →
fuel + depth ≥ Fintype.card α + 1 → G.bfs_dist_aux v fuel depth reached = G.dist u vdepth:ℕreached:Finset αh_inv:∀ (w : α), w ∈ reached ↔ w ∈ G.bfsStep^[depth] {u}h_not_found:∀ d < depth, v ∉ G.bfsStep^[d] {u}h_fuel:fuel + 1 + depth ≥ Fintype.card α + 1hv:v ∉ reachedh_inv':∀ (w : α), w ∈ G.bfsStep reached ↔ w ∈ G.bfsStep^[depth + 1] {u}⊢ fuel + (depth + 1) ≥ Fintype.card α + 1 omega All goals completed! 🐙)
computableDistMin agrees with distMin on a finite vertex set.
theorem distMin_eq_computableDistMin (G : SimpleGraph α) [DecidableRel G.Adj]
(S : Finset α) : distMin G (S : Set α) = computableDistMin G S := by α:Type u_1inst✝²:Fintype αinst✝¹:DecidableEq αG:SimpleGraph αinst✝:DecidableRel G.AdjS:Finset α⊢ G.distMin ↑S = G.computableDistMin S
unfold distMin computableDistMin α:Type u_1inst✝²:Fintype αinst✝¹:DecidableEq αG:SimpleGraph αinst✝:DecidableRel G.AdjS:Finset α⊢ (let pairs := {p ∈ (↑S).toFinset ×ˢ (↑S).toFinset | p.1 ≠ p.2};
if h : pairs.Nonempty then (Finset.image (fun p ↦ G.dist p.1 p.2) pairs).min' ⋯ else 0) =
let pairs := {p ∈ S ×ˢ S | p.1 ≠ p.2};
if h : pairs.Nonempty then (Finset.image (fun p ↦ G.computable_dist p.1 p.2) pairs).min' ⋯ else 0
simp only [Finset.toFinset_coe] α:Type u_1inst✝²:Fintype αinst✝¹:DecidableEq αG:SimpleGraph αinst✝:DecidableRel G.AdjS:Finset α⊢ (if h : {p ∈ S ×ˢ S | p.1 ≠ p.2}.Nonempty then (Finset.image (fun p ↦ G.dist p.1 p.2) ({p ∈ S ×ˢ S | p.1 ≠ p.2})).min' ⋯
else 0) =
if h : {p ∈ S ×ˢ S | p.1 ≠ p.2}.Nonempty then
(Finset.image (fun p ↦ G.computable_dist p.1 p.2) ({p ∈ S ×ˢ S | p.1 ≠ p.2})).min' ⋯
else 0
split_ifs pos α:Type u_1inst✝²:Fintype αinst✝¹:DecidableEq αG:SimpleGraph αinst✝:DecidableRel G.AdjS:Finset αh✝:{p ∈ S ×ˢ S | p.1 ≠ p.2}.Nonempty⊢ (Finset.image (fun p ↦ G.dist p.1 p.2) ({p ∈ S ×ˢ S | p.1 ≠ p.2})).min' ⋯ =
(Finset.image (fun p ↦ G.computable_dist p.1 p.2) ({p ∈ S ×ˢ S | p.1 ≠ p.2})).min' ⋯neg α:Type u_1inst✝²:Fintype αinst✝¹:DecidableEq αG:SimpleGraph αinst✝:DecidableRel G.AdjS:Finset αh✝:¬{p ∈ S ×ˢ S | p.1 ≠ p.2}.Nonempty⊢ 0 = 0
· pos α:Type u_1inst✝²:Fintype αinst✝¹:DecidableEq αG:SimpleGraph αinst✝:DecidableRel G.AdjS:Finset αh✝:{p ∈ S ×ˢ S | p.1 ≠ p.2}.Nonempty⊢ (Finset.image (fun p ↦ G.dist p.1 p.2) ({p ∈ S ×ˢ S | p.1 ≠ p.2})).min' ⋯ =
(Finset.image (fun p ↦ G.computable_dist p.1 p.2) ({p ∈ S ×ˢ S | p.1 ≠ p.2})).min' ⋯ congr 1 pos α:Type u_1inst✝²:Fintype αinst✝¹:DecidableEq αG:SimpleGraph αinst✝:DecidableRel G.AdjS:Finset αh✝:{p ∈ S ×ˢ S | p.1 ≠ p.2}.Nonempty⊢ Finset.image (fun p ↦ G.dist p.1 p.2) ({p ∈ S ×ˢ S | p.1 ≠ p.2}) =
Finset.image (fun p ↦ G.computable_dist p.1 p.2) ({p ∈ S ×ˢ S | p.1 ≠ p.2})
ext n pos α:Type u_1inst✝²:Fintype αinst✝¹:DecidableEq αG:SimpleGraph αinst✝:DecidableRel G.AdjS:Finset αh✝:{p ∈ S ×ˢ S | p.1 ≠ p.2}.Nonemptyn:ℕ⊢ n ∈ Finset.image (fun p ↦ G.dist p.1 p.2) ({p ∈ S ×ˢ S | p.1 ≠ p.2}) ↔
n ∈ Finset.image (fun p ↦ G.computable_dist p.1 p.2) ({p ∈ S ×ˢ S | p.1 ≠ p.2})
simp only [Finset.mem_image] pos α:Type u_1inst✝²:Fintype αinst✝¹:DecidableEq αG:SimpleGraph αinst✝:DecidableRel G.AdjS:Finset αh✝:{p ∈ S ×ˢ S | p.1 ≠ p.2}.Nonemptyn:ℕ⊢ (∃ a ∈ {p ∈ S ×ˢ S | p.1 ≠ p.2}, G.dist a.1 a.2 = n) ↔ ∃ a ∈ {p ∈ S ×ˢ S | p.1 ≠ p.2}, G.computable_dist a.1 a.2 = n
constructor pos.mp α:Type u_1inst✝²:Fintype αinst✝¹:DecidableEq αG:SimpleGraph αinst✝:DecidableRel G.AdjS:Finset αh✝:{p ∈ S ×ˢ S | p.1 ≠ p.2}.Nonemptyn:ℕ⊢ (∃ a ∈ {p ∈ S ×ˢ S | p.1 ≠ p.2}, G.dist a.1 a.2 = n) → ∃ a ∈ {p ∈ S ×ˢ S | p.1 ≠ p.2}, G.computable_dist a.1 a.2 = npos.mpr α:Type u_1inst✝²:Fintype αinst✝¹:DecidableEq αG:SimpleGraph αinst✝:DecidableRel G.AdjS:Finset αh✝:{p ∈ S ×ˢ S | p.1 ≠ p.2}.Nonemptyn:ℕ⊢ (∃ a ∈ {p ∈ S ×ˢ S | p.1 ≠ p.2}, G.computable_dist a.1 a.2 = n) → ∃ a ∈ {p ∈ S ×ˢ S | p.1 ≠ p.2}, G.dist a.1 a.2 = n
· pos.mp α:Type u_1inst✝²:Fintype αinst✝¹:DecidableEq αG:SimpleGraph αinst✝:DecidableRel G.AdjS:Finset αh✝:{p ∈ S ×ˢ S | p.1 ≠ p.2}.Nonemptyn:ℕ⊢ (∃ a ∈ {p ∈ S ×ˢ S | p.1 ≠ p.2}, G.dist a.1 a.2 = n) → ∃ a ∈ {p ∈ S ×ˢ S | p.1 ≠ p.2}, G.computable_dist a.1 a.2 = n rintro ⟨p, hp, rfl⟩ pos.mp α:Type u_1inst✝²:Fintype αinst✝¹:DecidableEq αG:SimpleGraph αinst✝:DecidableRel G.AdjS:Finset αh✝:{p ∈ S ×ˢ S | p.1 ≠ p.2}.Nonemptyp:α × αhp:p ∈ {p ∈ S ×ˢ S | p.1 ≠ p.2}⊢ ∃ a ∈ {p ∈ S ×ˢ S | p.1 ≠ p.2}, G.computable_dist a.1 a.2 = G.dist p.1 p.2
exact ⟨p, hp, (dist_eq_computable G p.1 p.2).symm⟩ All goals completed! 🐙
· pos.mpr α:Type u_1inst✝²:Fintype αinst✝¹:DecidableEq αG:SimpleGraph αinst✝:DecidableRel G.AdjS:Finset αh✝:{p ∈ S ×ˢ S | p.1 ≠ p.2}.Nonemptyn:ℕ⊢ (∃ a ∈ {p ∈ S ×ˢ S | p.1 ≠ p.2}, G.computable_dist a.1 a.2 = n) → ∃ a ∈ {p ∈ S ×ˢ S | p.1 ≠ p.2}, G.dist a.1 a.2 = n rintro ⟨p, hp, rfl⟩ pos.mpr α:Type u_1inst✝²:Fintype αinst✝¹:DecidableEq αG:SimpleGraph αinst✝:DecidableRel G.AdjS:Finset αh✝:{p ∈ S ×ˢ S | p.1 ≠ p.2}.Nonemptyp:α × αhp:p ∈ {p ∈ S ×ˢ S | p.1 ≠ p.2}⊢ ∃ a ∈ {p ∈ S ×ˢ S | p.1 ≠ p.2}, G.dist a.1 a.2 = G.computable_dist p.1 p.2
exact ⟨p, hp, dist_eq_computable G p.1 p.2⟩ All goals completed! 🐙
· neg α:Type u_1inst✝²:Fintype αinst✝¹:DecidableEq αG:SimpleGraph αinst✝:DecidableRel G.AdjS:Finset αh✝:¬{p ∈ S ×ˢ S | p.1 ≠ p.2}.Nonempty⊢ 0 = 0 rfl All goals completed! 🐙
theorem avg_dist_eq_computable (G : SimpleGraph α) [DecidableRel G.Adj] :
averageDistance G = (computable_avg_dist G : ℝ) := by α:Type u_1inst✝²:Fintype αinst✝¹:DecidableEq αG:SimpleGraph αinst✝:DecidableRel G.Adj⊢ G.averageDistance = ↑G.computable_avg_dist
unfold averageDistance computable_avg_dist α:Type u_1inst✝²:Fintype αinst✝¹:DecidableEq αG:SimpleGraph αinst✝:DecidableRel G.Adj⊢ (if Fintype.card α > 1 then (∑ u, ∑ v, ↑(G.dist u v)) / (↑(Fintype.card α) * (↑(Fintype.card α) - 1)) else 0) =
↑(if Fintype.card α > 1 then (∑ u, ∑ v, ↑(G.computable_dist u v)) / (↑(Fintype.card α) * (↑(Fintype.card α) - 1))
else 0)
split_ifs with h pos α:Type u_1inst✝²:Fintype αinst✝¹:DecidableEq αG:SimpleGraph αinst✝:DecidableRel G.Adjh:Fintype.card α > 1⊢ (∑ u, ∑ v, ↑(G.dist u v)) / (↑(Fintype.card α) * (↑(Fintype.card α) - 1)) =
↑((∑ u, ∑ v, ↑(G.computable_dist u v)) / (↑(Fintype.card α) * (↑(Fintype.card α) - 1)))neg α:Type u_1inst✝²:Fintype αinst✝¹:DecidableEq αG:SimpleGraph αinst✝:DecidableRel G.Adjh:¬Fintype.card α > 1⊢ 0 = ↑0
· pos α:Type u_1inst✝²:Fintype αinst✝¹:DecidableEq αG:SimpleGraph αinst✝:DecidableRel G.Adjh:Fintype.card α > 1⊢ (∑ u, ∑ v, ↑(G.dist u v)) / (↑(Fintype.card α) * (↑(Fintype.card α) - 1)) =
↑((∑ u, ∑ v, ↑(G.computable_dist u v)) / (↑(Fintype.card α) * (↑(Fintype.card α) - 1))) -- numerator equality
have hnum : (∑ u ∈ Finset.univ, ∑ v ∈ Finset.univ, (G.dist u v : ℝ)) =
↑(∑ u ∈ Finset.univ, ∑ v ∈ Finset.univ, (computable_dist G u v : ℚ)) := by α:Type u_1inst✝²:Fintype αinst✝¹:DecidableEq αG:SimpleGraph αinst✝:DecidableRel G.Adj⊢ G.averageDistance = ↑G.computable_avg_dist pos α:Type u_1inst✝²:Fintype αinst✝¹:DecidableEq αG:SimpleGraph αinst✝:DecidableRel G.Adjh:Fintype.card α > 1hnum:∑ u, ∑ v, ↑(G.dist u v) = ↑(∑ u, ∑ v, ↑(G.computable_dist u v))⊢ (∑ u, ∑ v, ↑(G.dist u v)) / (↑(Fintype.card α) * (↑(Fintype.card α) - 1)) =
↑((∑ u, ∑ v, ↑(G.computable_dist u v)) / (↑(Fintype.card α) * (↑(Fintype.card α) - 1)))
push_cast α:Type u_1inst✝²:Fintype αinst✝¹:DecidableEq αG:SimpleGraph αinst✝:DecidableRel G.Adjh:Fintype.card α > 1⊢ ∑ u, ∑ v, ↑(G.dist u v) = ∑ x, ∑ x_1, ↑(G.computable_dist x x_1) pos α:Type u_1inst✝²:Fintype αinst✝¹:DecidableEq αG:SimpleGraph αinst✝:DecidableRel G.Adjh:Fintype.card α > 1hnum:∑ u, ∑ v, ↑(G.dist u v) = ↑(∑ u, ∑ v, ↑(G.computable_dist u v))⊢ (∑ u, ∑ v, ↑(G.dist u v)) / (↑(Fintype.card α) * (↑(Fintype.card α) - 1)) =
↑((∑ u, ∑ v, ↑(G.computable_dist u v)) / (↑(Fintype.card α) * (↑(Fintype.card α) - 1)))
apply Finset.sum_congr rfl α:Type u_1inst✝²:Fintype αinst✝¹:DecidableEq αG:SimpleGraph αinst✝:DecidableRel G.Adjh:Fintype.card α > 1⊢ ∀ x ∈ Finset.univ, ∑ v, ↑(G.dist x v) = ∑ x_1, ↑(G.computable_dist x x_1)pos α:Type u_1inst✝²:Fintype αinst✝¹:DecidableEq αG:SimpleGraph αinst✝:DecidableRel G.Adjh:Fintype.card α > 1hnum:∑ u, ∑ v, ↑(G.dist u v) = ↑(∑ u, ∑ v, ↑(G.computable_dist u v))⊢ (∑ u, ∑ v, ↑(G.dist u v)) / (↑(Fintype.card α) * (↑(Fintype.card α) - 1)) =
↑((∑ u, ∑ v, ↑(G.computable_dist u v)) / (↑(Fintype.card α) * (↑(Fintype.card α) - 1))); intro u _ α:Type u_1inst✝²:Fintype αinst✝¹:DecidableEq αG:SimpleGraph αinst✝:DecidableRel G.Adjh:Fintype.card α > 1u:αa✝:u ∈ Finset.univ⊢ ∑ v, ↑(G.dist u v) = ∑ x, ↑(G.computable_dist u x)pos α:Type u_1inst✝²:Fintype αinst✝¹:DecidableEq αG:SimpleGraph αinst✝:DecidableRel G.Adjh:Fintype.card α > 1hnum:∑ u, ∑ v, ↑(G.dist u v) = ↑(∑ u, ∑ v, ↑(G.computable_dist u v))⊢ (∑ u, ∑ v, ↑(G.dist u v)) / (↑(Fintype.card α) * (↑(Fintype.card α) - 1)) =
↑((∑ u, ∑ v, ↑(G.computable_dist u v)) / (↑(Fintype.card α) * (↑(Fintype.card α) - 1)))
apply Finset.sum_congr rfl α:Type u_1inst✝²:Fintype αinst✝¹:DecidableEq αG:SimpleGraph αinst✝:DecidableRel G.Adjh:Fintype.card α > 1u:αa✝:u ∈ Finset.univ⊢ ∀ x ∈ Finset.univ, ↑(G.dist u x) = ↑(G.computable_dist u x)pos α:Type u_1inst✝²:Fintype αinst✝¹:DecidableEq αG:SimpleGraph αinst✝:DecidableRel G.Adjh:Fintype.card α > 1hnum:∑ u, ∑ v, ↑(G.dist u v) = ↑(∑ u, ∑ v, ↑(G.computable_dist u v))⊢ (∑ u, ∑ v, ↑(G.dist u v)) / (↑(Fintype.card α) * (↑(Fintype.card α) - 1)) =
↑((∑ u, ∑ v, ↑(G.computable_dist u v)) / (↑(Fintype.card α) * (↑(Fintype.card α) - 1))); intro v _ α:Type u_1inst✝²:Fintype αinst✝¹:DecidableEq αG:SimpleGraph αinst✝:DecidableRel G.Adjh:Fintype.card α > 1u:αa✝¹:u ∈ Finset.univv:αa✝:v ∈ Finset.univ⊢ ↑(G.dist u v) = ↑(G.computable_dist u v)pos α:Type u_1inst✝²:Fintype αinst✝¹:DecidableEq αG:SimpleGraph αinst✝:DecidableRel G.Adjh:Fintype.card α > 1hnum:∑ u, ∑ v, ↑(G.dist u v) = ↑(∑ u, ∑ v, ↑(G.computable_dist u v))⊢ (∑ u, ∑ v, ↑(G.dist u v)) / (↑(Fintype.card α) * (↑(Fintype.card α) - 1)) =
↑((∑ u, ∑ v, ↑(G.computable_dist u v)) / (↑(Fintype.card α) * (↑(Fintype.card α) - 1)))
simp [dist_eq_computable]pos α:Type u_1inst✝²:Fintype αinst✝¹:DecidableEq αG:SimpleGraph αinst✝:DecidableRel G.Adjh:Fintype.card α > 1hnum:∑ u, ∑ v, ↑(G.dist u v) = ↑(∑ u, ∑ v, ↑(G.computable_dist u v))⊢ (∑ u, ∑ v, ↑(G.dist u v)) / (↑(Fintype.card α) * (↑(Fintype.card α) - 1)) =
↑((∑ u, ∑ v, ↑(G.computable_dist u v)) / (↑(Fintype.card α) * (↑(Fintype.card α) - 1)))pos α:Type u_1inst✝²:Fintype αinst✝¹:DecidableEq αG:SimpleGraph αinst✝:DecidableRel G.Adjh:Fintype.card α > 1hnum:∑ u, ∑ v, ↑(G.dist u v) = ↑(∑ u, ∑ v, ↑(G.computable_dist u v))⊢ (∑ u, ∑ v, ↑(G.dist u v)) / (↑(Fintype.card α) * (↑(Fintype.card α) - 1)) =
↑((∑ u, ∑ v, ↑(G.computable_dist u v)) / (↑(Fintype.card α) * (↑(Fintype.card α) - 1)))
rw [hnum pos α:Type u_1inst✝²:Fintype αinst✝¹:DecidableEq αG:SimpleGraph αinst✝:DecidableRel G.Adjh:Fintype.card α > 1hnum:∑ u, ∑ v, ↑(G.dist u v) = ↑(∑ u, ∑ v, ↑(G.computable_dist u v))⊢ ↑(∑ u, ∑ v, ↑(G.computable_dist u v)) / (↑(Fintype.card α) * (↑(Fintype.card α) - 1)) =
↑((∑ u, ∑ v, ↑(G.computable_dist u v)) / (↑(Fintype.card α) * (↑(Fintype.card α) - 1))) pos α:Type u_1inst✝²:Fintype αinst✝¹:DecidableEq αG:SimpleGraph αinst✝:DecidableRel G.Adjh:Fintype.card α > 1hnum:∑ u, ∑ v, ↑(G.dist u v) = ↑(∑ u, ∑ v, ↑(G.computable_dist u v))⊢ ↑(∑ u, ∑ v, ↑(G.computable_dist u v)) / (↑(Fintype.card α) * (↑(Fintype.card α) - 1)) =
↑((∑ u, ∑ v, ↑(G.computable_dist u v)) / (↑(Fintype.card α) * (↑(Fintype.card α) - 1)))]pos α:Type u_1inst✝²:Fintype αinst✝¹:DecidableEq αG:SimpleGraph αinst✝:DecidableRel G.Adjh:Fintype.card α > 1hnum:∑ u, ∑ v, ↑(G.dist u v) = ↑(∑ u, ∑ v, ↑(G.computable_dist u v))⊢ ↑(∑ u, ∑ v, ↑(G.computable_dist u v)) / (↑(Fintype.card α) * (↑(Fintype.card α) - 1)) =
↑((∑ u, ∑ v, ↑(G.computable_dist u v)) / (↑(Fintype.card α) * (↑(Fintype.card α) - 1)))
push_cast pos α:Type u_1inst✝²:Fintype αinst✝¹:DecidableEq αG:SimpleGraph αinst✝:DecidableRel G.Adjh:Fintype.card α > 1hnum:∑ u, ∑ v, ↑(G.dist u v) = ↑(∑ u, ∑ v, ↑(G.computable_dist u v))⊢ (∑ x, ∑ x_1, ↑(G.computable_dist x x_1)) / (↑(Fintype.card α) * (↑(Fintype.card α) - 1)) =
(∑ x, ∑ x_1, ↑(G.computable_dist x x_1)) / (↑(Fintype.card α) * (↑(Fintype.card α) - 1))
ring All goals completed! 🐙
· neg α:Type u_1inst✝²:Fintype αinst✝¹:DecidableEq αG:SimpleGraph αinst✝:DecidableRel G.Adjh:¬Fintype.card α > 1⊢ 0 = ↑0 simp All goals completed! 🐙
distEven G v counts the vertices at even distance from v in G. This is
DeLaVina's dist_even(v) invariant appearing in several WOWII conjectures.
Distance zero is even, so v itself is always counted.
noncomputable def distEven (G : SimpleGraph α) (v : α) : ℕ :=
(Finset.univ.filter fun w => Even (G.dist v w)).cardThe set of pairs of distinct vertices with even distance > 0.
noncomputable def evenDistancePairs (G : SimpleGraph α) : Finset (α × α) :=
Finset.univ.filter (fun p => G.dist p.1 p.2 % 2 = 0 ∧ G.dist p.1 p.2 > 0)
Minimum even distance between distinct vertices in G.
Only positive even distances are considered. Returns 0 if no such distance exists.
noncomputable def minEvenDistance (G : SimpleGraph α) : ℕ :=
letI pairs := G.evenDistancePairs
if h : pairs.Nonempty then
letI dists := pairs.image (fun p => G.dist p.1 p.2)
(dists.min' (Finset.Nonempty.image h _))
else 0
Maximum even distance between distinct vertices in G.
Only positive even distances are considered. Returns 0 if no such distance exists.
noncomputable def maxEvenDistance (G : SimpleGraph α) : ℕ :=
letI pairs := G.evenDistancePairs
if h : pairs.Nonempty then
letI dists := pairs.image (fun p => G.dist p.1 p.2)
(dists.max' (Finset.Nonempty.image h _))
else 0
Average even distance between distinct vertices in G.
Only positive even distances are considered. Returns 0 if no such distance exists.
noncomputable def averageEvenDistance (G : SimpleGraph α) : ℚ :=
letI pairs := G.evenDistancePairs
if pairs.card > 0 then
(∑ p ∈ pairs, (G.dist p.1 p.2 : ℚ)) / (pairs.card : ℚ)
else 0end SimpleGraph