Let's call a simple graph $g$ magnificent if and only if:
- $g$ is connected
- $g$ has at least two vertices of degree $> 1$
- For every vertex $v$ of degree $> 1$, the degree of $v$ is unique among vertices of $g$.
I picked this property because it can be stated using the degree multiset and because the property is very non-local. Also, any connected graph with at least one edge can be made magnificent by attaching varying amount of "fuzz" (edges going to fresh vertices) to each of its vertices.
Here's a game that we can play on a set of vertices.
Player 1 and player 2 take turns choosing edges that haven't been chosen before on a $K_n$. A player loses if they can't make a move.
Additionally, a player wins if at the end of their turn the current board $g$ contains as one of its connected components a magnificent graph.
For sets of vertices of size $1, 2, 3, 4$, no magnificent graphs are possible. So, player 1 wins if and only if ${n \choose 2}$ is odd, i.e. $n \equiv_4 2$ or $n \equiv_4 3$.
For a set of $5$ vertices, ${5 \choose 2} = 10$, so player 2 will win if neither player manages to make a magnificent component.
There's one magnificent graph up to isomorphism on five vertices $\{AB, BC, CD, CE, CF\}$.
This graph doesn't contain a triangle, and uses all the vertices. So, if player 2 can create a triangle, then they win.
Without loss of generality, let player 1's first move be $AB$. Let player 2 pick $BC$. Player can't win by picking $BD$ since that graph only has a single vertex of degree strictly greater than one and can't win by picking $CD$ since the degrees of the vertices $B$ and $C$ are the same in in $AB, BC, CD$. So player 2 can build their triangle during their second turn.
The player associated with the parity of ${ n \choose 2}$ clearly has a distinct advantage.
My question is: do they always win?
I think they do. We will need the observation that a magnificent graph must contain at least three vertices of degree $1$ (good mini-exercise).
Let's start with the case when $\binom{n}{2}$ is even. We are going to describe a winning strategy for player 2. More precisely, if $n$ is odd, then player 2 will force the creation of a magnificent connected component on five vertices, while if $n$ is even, then the players will exhaust all the edges.
Let player 1 start with the edge $ab$. Player 2 will choose a disjoint edge $cd$. The important observation now is that the next edge $ef$ that player 1 chooses must be disjoint from $ab$ and $cd$. Indeed, otherwise the chosen edge, without loss of generality, is either $ac$, or $ae$ for some unused vertex $e$. But then player 2 can form the subgraph (induced by) $ab,ac,ae,cd$, which is magnificent.
By the same reasoning, the players must keep choosing disjoint edges until the vertices run out. Because $n$ is equal to $0$ or $1$ modulo $4$, player 2 will be the last one to choose an edge. If $n$ is odd, then the next edge of player 1 is either of the form $ax$ for the single unused vertex $x$, or $ac$ for some already used vertices $a,c$. As before, player 2 can win by choosing $ac$ or $ax$, respectively. So let us suppose that $n$ is even. At this point, our graph is a perfect matching: every vertex $v$ has a pair $f(v)$. For the rest of the game, whenever player 1 chooses an edge $uv$, player 2 will choose $f(u)f(v)$. You can check that with this strategy at no point of the game can there be a connected component with more than two degree $1$ vertices, so no magnificent connected components will be created.
Now let us consider the case when $\binom{n}{2}$ is odd. Again, player 1 chooses $ab$. If player 2 were to choose a disjoint edge $cd$, then as before, they must keep choosing disjoint edges until the vertices run out. In this case player 1 wins with the same strategy as player 2 before. So we may assume that player 2 chooses $bc$. Then player 1 will choose $ac$ to create a triangle (the only non-losing choice, actually). From now on, player 1 can ensure that after each move he or she makes, there is only one non-trivial connected component, which contains at most one vertex of degree $1$. It is not difficult but somewhat fiddly to work out how to do this so I'll leave out the details. It follows that player 2 cannot make a component that contains at least three degree $1$ vertices, since each move adds at most one degree $1$ vertex to the non-trivial component (or creates a new non-trivial component consisting of a single edge, which player 1 will merge into the large component in the next turn). Thus, no magnificent connected components will be created, and so the edges will run out and player 1 will win.