2.If t E Nk+1(s),then d(s,t)=k+1 Recall:Ni(s)={all neighbors of Ni-1(s)}-Ni-1(s)-..-Ni(s)-{s} ■d(s,t)≤k+1:Why? since t is a neighbor of some vertex t'∈Nk(s), 2 d(s,t)=k by induction. ■d(s,t)≥k+1:Why? d(s,t)won't be k since otherwise it'd have been covered by some Ni(s)with i≤k.(By induction) 172. If 𝑡 ∈ 𝑁𝑘+1(𝑠), then 𝑑(𝑠,𝑡) = 𝑘 + 1 ◼ 𝑑(𝑠,𝑡) ≤ 𝑘 + 1: Why? since 𝑡 is a neighbor of some vertex 𝑡′ ∈ 𝑁𝑘(𝑠), ❑ 𝑑(𝑠,𝑡′) = 𝑘 by induction. ◼ 𝑑(𝑠,𝑡) ≥ 𝑘 + 1: Why? 𝑑(𝑠,𝑡) won’t be ≤ 𝑘 since otherwise it’d have been covered by some 𝑁𝑖(𝑠) with 𝑖 ≤ 𝑘. (By induction) s t t’ 1 2 k Recall:𝑁𝑖 (𝑠) = {all neighbors of 𝑁𝑖−1 (𝑠)} − 𝑁𝑖−1 (𝑠) − ⋯ − 𝑁1 (𝑠) − {𝑠} 17