Proof of Nk(s)={v:d(v,s)=k} Let's prove this by induction on k. k =1:trivially true. 2 0飞 Suppose k is correct, consider k+1.Need: 1.If d(s,t)=k +1,then t E Nk+1(s) ▣2.Ift∈Nk+1(s),then d(S,t)=k+1 15Proof of 𝑁𝑘(𝑠) = {𝑣: 𝑑(𝑣, 𝑠) = 𝑘} ◼ Let’s prove this by induction on 𝑘. ◼ 𝑘 = 1: trivially true. ◼ Suppose 𝑘 is correct, consider 𝑘 + 1. Need: ❑ 1. If 𝑑(𝑠,𝑡) = 𝑘 + 1, then 𝑡 ∈ 𝑁𝑘+1(𝑠) ❑ 2. If 𝑡 ∈ 𝑁𝑘+1(𝑠), then 𝑑(𝑠,𝑡) = 𝑘 + 1 s 1 2 k t 15