## 5.5 Distances in *n*-Cubes

In this section we analyze for which probabilities, λ_{n}, random induced subgraphs of *n*-cube exhibit “short” distances. To be precise, we ask for which λ_{n} does there exist some constant *Δ* such that

Before we give the main result of this section we prove a combinatorial lemma [21]. A weaker version of this lemma is proved in [6].

**Lemma 5.8** *Let d*∈ ,*d* ≥ 2, *and let v, v′ be two Q*^{n}_{2}-vertices where d(*v, v*′) = *d. Then any Q*^{n}_{2}-path from *v* to *v*′ has length 2*l* + *d, and there are at most*

*Q*^{n}_{2}-paths from *v* to *v*′ *of length* 2*l* + *d*.

*Proof*. W.l.o.g. we can assume *v* =(0,...,0) and *v*′ =(*x*_{i})_{i}, where *x*_{i}=1 for 1 ≤ *i* ≤ *d*, and *x*_{i} = 0 otherwise. Each path of length *m* induces the family of steps (ε_{s})_{1≤s≤m}, where ε_{s}∈{*e*_{j}| 1 ≤ *j* ≤ *n*}. Since the path ends at *v*′, we have for fixed 1 ≤ *j* ≤ *n*

Hence the families induced by our paths contain necessarily the set {*e*_{1},..., *e*_{d}}. Let (ε′_{s})_{1≤s≤m′} be the family obtained from (ε_{s})_{1≤s≤m} by removing the steps *e*_{1},..., *e*_{d} at the smallest index at which they occur. Then (ε′_{s})_{1≤s≤m′} represents a cycle starting and ending at *v*. Furthermore, we have for all