Hence, σ(Q,v) ≤ σ(Q,v,). Suppose σ(Q,v) = σ(Q,v,). Then, all agents in the path from
v′ to v form part of a cycle at this step. Since an agent can be part of at most one cycle
at a given step, all agents in the path from v, to v are in the same cycle. ■
Lemma B.7 Let Q ∈ QI. Let i ∈ I and Qti ∈ Q. Define Q := (Qi,Q-i). Suppose
τ(Q)(i) = τ(Q')(i) and σ(Q,i) ≤ σ(Q,,i). Then, for each step l with σ(Q,i) ≤ l ≤
σ(Q,,i), if v ∈ V(Q,,l)∖(P(Q',l,i) ∪ i) then v ∈ V(Q,l) and F(Q,l,v) = F(Q,,l,v).28
Proof Let p := σ(Q, i) and p, := σ(Q', i). From Lemma B.3(b),
V(Q,p) = V(Q,,p) and qQ,p = qQ',p for each school s ∈ V(Q,p) ∩ S. (1)
With a slight abuse of notation, for each l, p ≤ l ≤ p, denote Pl = P(Q,, l, i) ∪ i. From
Observation B.1,
Pp ⊆ Pp+1 ⊆∙∙∙⊆ Pp'-1 ⊆ Pp'. (2)
Also note
V(Q,,p,) ⊆ V(Q',p' - 1) ⊆∙∙∙⊆ V(Q,p + 1) ⊆ V(Q,p). (3)
We are done if we prove the following Claim(l) for each l, p ≤ l ≤ p′.
Claim(l): If v ∈ V(Q,, l)\Pl, then v ∈ V(Q, l) and e(Q, l, v) = e(Q,, l, v).
Indeed, Claim(l) immediately implies the following Consequence(l):
Consequence(l): Ifv ∈ V (Q,, l)\Pl, then v ∈ V(Q,l) and F(Q,l,v) = F (Q,, l, v).
We now prove by induction that Claim(l) is true for each l, p ≤ l ≤ p,. By Lemma B.3(b,c),
V(Q, p) = V(Q,, p) and e(Q, p, v) = e(Q,, p, v) for each agent v ∈ V(Q, p)\i. Hence,
Claim(p) is true.
If p, = p we are done. So, suppose p, = p. Let l be a step such that p < l ≤ p,.
Assume Claim(g) is true for all g, p ≤ g < l ≤ p,. We prove that Claim(l) is true. Let
v ∈ V(Q,, l)\Pl. From (2) and (3), v ∈ V(Q,, g)\Pg for each step g, p ≤ g < l. From
Consequence(g) (p ≤ g < l), v ∈ V(Q, g) and
F(Q, g, v) = F(Q,, g, v) for each step g, p ≤ g < l. (4)
Since v ∈ V (Q,, l), v is not removed at the end of step l - 1 in TTC(Q,). Then by (1)
and (4), v is also not removed at the end of step l - 1 in TTC(Q). Hence, v ∈ V(Q, l).
28It follows immediately from the proof that the directed paths associated with F(Q, l, v) and F(Q', l, v)
in V(Q, l) and V(Q', l), respectively, also coincide.
36