ELMO SL 2019 C2

Adithya and Bill are playing a game on a connected graph with $n > 2$ vertices, two of which are labeled $A$ and $B$ , so that $A$ and $B$ are distinct and non-adjacent and known to both players. Adithya starts on vertex $A$ and Bill starts on $B$ . Each turn, both players move simultaneously: Bill moves to an adjacent vertex, while Adithya may either move to an adjacent vertex or stay at his current vertex. Adithya loses if he is 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 number of edges the graph may have? (Your answer may be in terms of $n$ .)

Proposed by Steven Liu