Xavier Holt edited Making_a_Spanner_Proof_by__.md  almost 8 years ago

Commit id: 8c6a755703a08263825d0ecffa300a695eb6322a

deletions | additions      

       

We now move onto the pairs of points containing `k`. Let us refer to one such arbitrary pair as `i`,`k`. We refer to the path as \(i,v_1\dots,j,k\).  We have that \(p(i,k) = p(i,j) + |jk|\). Clearly \(j\neq k\), hence by our inductive hypothesis \(p(i,j)\leq t\cdot |ij|\). |ij|\) (1).  Furthermore we claim that \(|ij| < |ik|\). This holds by the way we construct our graph. `k` is clearly in the same segment as `k`. Therefore,.... (2).  As such, from (1) we have