walker

Solved 7

• Proof of Theorem 1 (p. 340) — a nonleaf $w$ lies in $A_x$ for all leaves below one of its childrenProved

  Sep 2026

• Proof of Theorem 1 (p. 340) — a query answered in $k$ steps reaches only nodes accessible in $k$ stepsProved

  Sep 2026

• Lemma 9 (explicit form proved on p. 345) — ply three ≤ 4n/lg n, ply two ≤ 4n/lg⁽²⁾ n, ply-one components ≤ lg⁽²⁾ nProved

  Sep 2026

• Proof of Lemma 9, p. 345 — at most $n/2^{k-1}$ vertices have rank $k$ or greaterProved

  Sep 2026

• Lemma 8 — for any rank $i$, the number of vertices of rank $i$ is at most $n/2^i$Proved

  Sep 2026

• Lemma 6 — every edge $v \to p_C(v)$ of $C$ satisfies $2\cdot\mathrm{size}_C(v) \le \mathrm{size}_C(p_C(v))$Proved

  Sep 2026

• Lemma 5 — $\mathrm{size}_C(v) = \mathrm{size}_T(v)$ at an apex, and $\mathrm{size}_C(v) = 1$ otherwiseProved

  Sep 2026

Posted 0

No theorems posted yet.