First player always wins. In the first three moves, player $1$ forms a triangle, ex: player $1$ makes edge $(1,2),$ then player $2$ makes edge $(2,3)$ and then player $1$ makes edge $(3,1).$ If $n=3$ then player $1$ wins already. Now player $1$ picks two of those three vertices, wlog $1,2.$ The remainder of the game will be played on $K_{2,n-3},$ the complete bipartite graph with one side being vertices $1,2,$ and the other side containing the other $n-3$ vertices ($4 \ldots n$) Note that there are an even number of edges in $K_{2,n-3}.$ Now it is player $2$'s turn. Observe the following sequence of four moves: Player $2$ makes the move $(1,k), k \in [4,n].$ Then Player $1$ makes the move $(k,2).$ Player $2$ then makes the move $(2,j), j \in [4,n], j \neq k.$ And finally Player $1$ makes the move $(j,1).$ Repeat the following sequence moves again. Clearly by playing like this Player $1$ ensures that the game is played on $K_{2,n-3}.$ And after each sequence of four such moves, it is equivalent to deleting $2$ of the vertices from $[4,n],$ ie. the game is now played on $K_{2,n-5},$ and it is again player $2$'s turn. Now if $n-3$ is even, eventually all of the vertices will be used up in these sequences of four moves (with two being removed each time.) So eventually player $2$ runs out of moves. Or if $n-3$ is odd, eventually there will be one vertex $i \in [4,n]$ left and player $2$ must make the move $(1,i),$ and player $1$ moves $(i,2),$ and player $2$ is again out of moves. Thus, player $1$ always win under optimal play. Edit: Actually after looking at this again I realized you don't need the triangle at the start; player $1$ just forms an edge $(1,2)$ and then the game is played on $K_{2,n-2},$ by similar reasoning as before and again player $1$ always wins.