I was inventing a problem for a math contest, I was really pleased with it, but then I found a mistake in my solution and have not been able to solve it. It is as follows:
Alice and Bob play a game. Let $n$ be a fixed positive integer. Alice selects a connected simple graph on $n$ vertices. After this Alice and Bob take turns selecting a vertex with at least $1$ adjacent edge and removing all the edges adjacent to it. Bob starts. For which values of $n$ does Bob always have a strategy that allows him to take strictly more edges than Alice?
I have found it is possible for $n=2,3,5$ and that it is not possible for $n=1$ and every even integer above $2$ (Alice can select $K_{2,n-2}$). It remains to be seen if there is a non-trivial graph on an odd number of vertices that works.
Some trivial observations:
Bob can always take the graph with the highest degree every turn. For a graph to be able to resist this strategy it must have at least two vertices with the highest possible degree which are non-adjacent; the graph must also have an even number of edges.
We can also define $B(G)$ as the maximum possible difference between the number of edges for Bob and Alice that Bob can guarantee. We are then looking for graphs with $B(G)=0$. It is clear $B(G)=\max(d(v)-B(G - v))$, where $v$ is any vertex in $G$ and $d(v)$ is the degree of $v$.