Redacted

Afo wrote: After giving a construction, can't we just say that it's trivial that the degree of $B$ is at most $1$ You can of course say this, but it is neither trivial nor true: On the 4-cycle $A-x-B-y-A$, Adithya does have a winning strategy and the number of edges is $4={4-1\choose2}+1$. However, the degree of $B$ is NOT at most $1$.

Redacted

This problem is so cute,love it. So here is my solution(anyway very similar to #2) First we guess that the answer is $\boxed{\binom{n-1}{2} + 1}.$,We have 2 main claims that will help us solve the problem $Calim 1.$. $B$ will always win if $B$ can form a triangle connecting his vertex and 2 other connected vertices. $Proof$ ;Since B can see where $A$ will be ,then using his starting vertice $B$ and the other two connected ones with $B$ (to forme a triangle),at which time he wants he can be at any positions he wants,(in these 3 points that forms a triangle),so basicly $A$ will never win. $Claim 2.$. ,Let us take $n-1$ vertixes appart from $B$,and take an edge between every pair of them.Let $B$ be connected to a vertex $C$ ,from $Claim .1.$ we know that $B$ can not be connected to any other vertex other than $C$,so $A$ will make the following move to guarantee that he will win. $A-->A-->C-->B$ ,since $B$ is always in the move ,he can never get to his starting positions in 3 moves,and $A$ will always win from this confiraguration. From $Claim 2$ we get that $\binom{n-1}{2} + 1$,also from $Claim 1.$ we get that since no two of these $k$ vertixes may be connected with each other (otherwise A will lose) we get that $\binom{n-1}{2} - \binom{k}{2}$ edges appart from $B$ can be made. Thus, we get the upper bound $k + \binom{n-1}{2} - \binom{k}{2} = \binom{n-1}{2} - \frac{k^2 - 3k}{2} \leq \binom{n-1}{2} + 1,$ $\blacksquare$

Redoing it, since the previous one is a fake-solve. Solution. The answer is $\binom{n-1}{2}+1$. The construction is to make a complete graph out of all vertices except $B$ and add an edge between $B$ to any other vertex $\neq A$. This is possible since $n \ge 3$. Claim 1. There is no triangle containing $B$ Proof. If there is, Bill can go to $B$ in the $i^{th}$ move for any $i=2,3,\dots$. $\blacksquare$ Let there be exactly $k$ vertices adjacent to $B$. The graph contains at most $\binom{n}{2}$ edges. However, it is necessary that the $k$ vertices are not adjacent to one another by Claim 1. It's also necessary that the other $n - k - 1$ vertices (The vertices that are not adjacent to $B$ or is $B$ itself) can't be adjacent to $B$. So the graph contains at most $\binom{n}{2} -\binom{k}{2} - (n-k-1)$ edges. We finish the problem by showing $$\binom{n}{2} -\binom{k}{2} - (n-k-1) \leq \binom{n-1}{2}+1$$$$\iff (k-1)(k-2) \ge 0$$ Remark. This is the same as the other solutions since $$\binom{n}{2} -\binom{k}{2} - (n-k-1) = k + \binom{n-1}{2} - \binom{k}{2}$$

Let a reverse edge be an unordered pair of vertices that aren't connected. We claim the minimum number of reverse edges is $n-2$. The construction for $n-2$ reverse edges is a $K_{n-1}$ with a leaf. Let the leaf be $VB$ where $B$ has degree $1$. Adithya's strategy is simply to stay at $A$, move to $V$, then move to $B$, which clearly works. Lemma: In a graph on $n$ vertices with at most $n-3$ reverse edges, every vertex is part of a triangle. Proof: Suppose, towards contradiction, that a vertex $V$ of degree $k$ is not part of a triangle. Then the graph has at least $n - 1 - k + \binom{k}{2}\ge n - 1 - k + (k-1) = n-2$ reverse edges, a contradiction and the lemma is established. By the lemma, we know that $B$ is part of a triangle. In particular, Bill can reach $B$ again in $2$ moves or $3$ moves, and hence $m$ moves for all $m\ge 2$ by induction. Since $A$ and $B$ are not adjacent this means Adithya cannot possibly have a winning strategy, as desired.