= Solution
Let $C$ be the final `A` <set> produced by the <algorithm>. It contains the initial `A` set, and every <vertex> outside $C$ has at most half its neighbours in $C$: otherwise its final key would still be positive. Thus $C$ is closed under the activation rule.
Now consider \i[any] legal sequence, including sequences which change some `A` preferences back to `B`. We prove by <induction> that its current `A` set is always a <subset> of $C$. This is true initially. A switch to `B` preserves the inclusion. If a <vertex> outside $C$ were to switch to `A`, its `A` neighbours would all lie in $C$, so their number could not exceed half its degree. Such a switch is forbidden. A switch inside $C$ also preserves the inclusion.
Consequently every attainable final `A` set has size at most $|C|$. The <algorithm> supplies a legal sequence attaining $C$ itself, so \b[its sequence is optimal]. This <closure dominance for asynchronous threshold switching> proves more than a local-greedy claim: temporary losses of `A` <vertices> cannot unlock an additional <vertex> outside the activation closure.
Back to article page
