When dealing with movements to adjacent vertices in a graph-based game, it is often useful to consider matchings in the graph. This problem is no exception.

In conclusion:

\[\text{Bob wins} \iff \text{The tree has a perfect matching}\]

Determining the existence of a perfect matching in a tree can be done in \(O(N)\) time using a greedy algorithm that adopts edges connected to leaves.

Below is the proof.

Proof

\((\impliedby)\)

Assume the tree has a perfect matching. On Bob’s turn after Alice marks a vertex, Bob can always choose the vertex matched to the one Alice marked previously.

\((\implies)\)

We will prove the contrapositive: if the tree does not have a perfect matching, Alice can win. Select a root \(r\) and consider the tree as a rooted tree. Let’s observe the method for solving the maximum matching by greedily adopting edges connected to leaves. Starting with an empty matching, proceed as follows for vertices in order of increasing depth:

• If the vertex is already part of the matching, do nothing.
• Otherwise, if its parent exists and is not yet part of the matching, match it with its parent.
• If neither of the above applies, the vertex is not included in the maximum matching.

The following is the pseudocode for this process. yet represents how many times vertex v can still be used. matching(v) returns whether vertex v remains unmatched when the greedy matching is applied.

# matching(r) == 0 iff the tree has a perfect matching
int matching(int v):
    yet = 1
    for c in children of v:
        yet -= matching(c)
    if yet < 0:
        # not a perfect matching
        return inf
    else:
        return yet

If the tree does not have a perfect matching, executing matching(r) in the pseudocode leads to one of the following cases:

• 1 is returned.
• The if yet < 0 branch is executed.

First Case: 1 is Returned

In this case, Alice can win by initially selecting the root \(r\). The graph obtained by removing \(r\) from the tree has a perfect matching. By the same argument as in \((\impliedby)\), if the roles of Alice and Bob are reversed, Alice is guaranteed to win.

Second Case: if yet < 0 is Executed

Now, consider the point where the if yet < 0 branch is executed for the first time. Let this vertex be \(v\). There must be at least two children \(c_1\) and \(c_2\) of \(v\) such that matching(c) returns \(1\) (since the branch yet < 0 implies that there are at least two such vertices). In this situation, Alice can win by initially selecting \(c_1\).

Now, focus on the graph \(G\) that consists of \(v\) and the subtrees rooted at \(c_1\) and \(c_2\). The graph obtained by removing \(c_1\) from \(G\) has a perfect matching. By the same argument as before, Bob will be forced to make the first move where no further moves are possible within \(G\).

Since \(v\) is the boundary between \(G\) and the rest of the tree, Bob will be forced to mark \(v\). When the play extends outside \(G\), Bob will need to mark a vertex connected to \(v\), leading to a position where he cannot make a valid move and ultimately loses. Therefore, this strategy ensures a winning move for Alice.

This completes the proof of \(\implies\).