Given $2n$ people in a room where each pair is either friends or strangers, two players take turns picking a person such that the person chosen is a friend of the person previously picked. The player who cannot make a move loses. Determine a winning strategy for one of the players.
What I think,
Let A and B be the first and second player respectively.
Each vertex of Graph G represents the person and two vertices are connected if they are friends.
A wins if the graph has two connected edges, three connected edges in a triangle.
B wins if the graph has one edge, three connected edges in a line.
Hint: if there is a perfect matching of the graph, B wins. Otherwise A wins.
Edit: in response to an extended discussion below, aiming to settle the precise statement of the problem, I will try to provide a more robust solution.
Case 1: Player A gets to choose the starting vertex, then B chooses an adjacent vertex and the game continues.
Suppose there is a perfect matching. Then no matter which vertex A chooses, B can go along an edge to a matched vertex and continue this way, so he will always be able to make a move.
Now suppose there is no perfect matching. Then A can find any maximum matching, then pick an unmatched vertex and use the strategy of B above, i.e. to always pick the vertex matched with the vertex chosen by B. This way A will win, for if B could at one time pick an unmatched vertex, the path traversed throughout the game would form an augmenting path, but such a path never exists in a maximum matching.
Case 2: The starting vertex $u \in G$ is arbitrarily fixed and A plays first by choosing a friend of $u$.
Suppose there is a maximum matching omitting $u$. Then the winning strategy for B is analogous to the one in the case 1.
Suppose on the contrary that every maximum matching involves $u$. Then A can pick any maximum matching and play as before, i.e. always choose a vertex matched to the one chosen by B. It is always possible: if B could once choose an unmatched vertex $v$, the traversed path would be an alternating path beginning in $u$ and ending in $v$. By shifting the edges along that path we produce a maximum matching omitting $u$, which was assumed to be impossible. So A wins.
Case 3: We are at a fixed vertex $u \in G$ at some point in a game in progress. Since the already used vertices are no longer of use to us, we can remove them from $G$, thereby reducing the case to the previous one.