C2. Adithya and Bill are playing a game on a connected graph with $n>2$ vertices and $m$ edges. First, Adithya labels two of the vertices $A$ and $B$, so that $A$ and $B$ are distinct and non-adjacent, and announces his choice to Bill. Then Adithya starts on vertex $A$ and Bill starts on $B$.

Now the game proceeds in a series of rounds in which both players move simultaneously. In each round, Bill must move to an adjacent vertex, while Adithya may either move to an adjacent vertex or stay at his current vertex. Adithya loses if he is ever on the same vertex as Bill, and wins if he reaches $B$ alone. Adithya cannot see where Bill is, but Bill can see where Adithya is.

Given that Adithya has a winning strategy, what is the maximum possible value of $m$, in terms of $n$ ?
(Steven Liu)
The answer is $m=\binom{n-1}{2}+1$. Here is the solution by Milan Haiman.
Construction: suppose $G$ consists of an $(n-1)$-clique, two of the vertices which are labeled $C$ and $A$, with one extra leaf attached to $C$, which we label $B$. Then, Adithya wins by starting at $A$ and following the sequence $A \rightarrow A \rightarrow C \rightarrow B$.

Bound: The main lemma is the following.
Claim - If $B$ is part of any triangle, then Adithya can't guarantee victory.
Proof. Bill can move among those three vertices and arrive back at $B$ after $k$ moves, for any $k \geq 2$. Moreover Adithya takes at least two moves to reach $B$.

So if Adithya is to win, we must have
$$
m \leq\left(\binom{n-1}{2}-\binom{d}{2}\right)+d
$$
where $d$ is the degree of $B$, and this implies the result.