Xavier Holt edited Making_a_Spanner_Proof_by__.md  almost 8 years ago

Commit id: a6e9594a1e79c47b98aab5bfbc74fe2a0b9c9118

deletions | additions      

       

### Inductive Hypothesis  Assume that \(G(t)\) is a t-spanner for \(n-1\) points.   ### Inductive Step: RTP Step  RTP:  \(G(t)\) is a t-spanner for \(n\) points. #### Notation  Let `k` be the point added as part of our inductive step. Let \(p(i,j)\) refer to the length of the t-path connecting i and j. We adopt the following strategy for constructing an `i,j` t-path. Assume WLOG we start from `i`. At every step, we choose the edge whose end-point lies in the same segment as `j`.