for some $0 \le i \le M-1$. Recall that $d(v,t) \leq R/2$ (by definition and construction of $T_i(v)$). Consider a vertex $c$ in $C$. As $v$ and $c$ are on a cycle of length $R$ we have $d(c,v) \leq R$ and therefore $d(c,t) \leq d(c,v) + d(v,t) \leq 3R/2$ by triangle inequality. It follows by construction that each vertex $c \in C$ with $d(v,c)\leq R/2$ will be added to $A_v$ as desired.

With the correctness of ${\textsc{GirthApprox}}$ (\[algo:girth3\]) established, in the remainder of this section we focus on analyzing its running time. To do this we will consider an invocation of ${\textsc{SimilarSet}}$ (\[alg:similar\_vertices\]) and both bound its running time and the size of the sets $A_v$ it computes.

Before setting up the proofs, for each vertex $v \in V$ we define $$G_0(v) = \{s \in V \mid d(v, s) \le R/2 \}$$ and $$G_i(v) = \{s \in V \mid d(v, s) \le R/2 \text{ and }
d(s, t) \le 3R/2 \text{ for all } t\in \cup_{0 \le j \le i-1}{R_{j}(v)}\} ~.$$ Notice that the distribution of $T_i(v)$ is the distribution on vertices that results from taking each $s \in G_i(v)$ and including it in $T_i(v)$ with probability $p = 1/\sqrt{n}$.

