Question 38
Given a (simple) graph $G$ with $n \geq 2$ vertices $v_{1}, v_{2}, \ldots, v_{n}$ and $m \geq 1$ edges, Joël and Robert play the following game with $m$ coins:
i) Joël first assigns to each vertex $v_{i}$ a non-negative integer $w_{i}$ such that $w_{1}+\cdots+w_{n}=m$.
ii) Robert then chooses a (possibly empty) subset of edges, and for each edge chosen he places a coin on exactly one of its two endpoints, and then removes that edge from the graph. When he is done, the amount of coins on each vertex $v_{i}$ should not be greater than $w_{i}$.
iii) Joël then does the same for all the remaining edges.
iv) Joël wins if the number of coins on each vertex $v_{i}$ is equal to $w_{i}$.
Determine all graphs $G$ for which Joël has a winning strategy.
i) Joël first assigns to each vertex $v_{i}$ a non-negative integer $w_{i}$ such that $w_{1}+\cdots+w_{n}=m$.
ii) Robert then chooses a (possibly empty) subset of edges, and for each edge chosen he places a coin on exactly one of its two endpoints, and then removes that edge from the graph. When he is done, the amount of coins on each vertex $v_{i}$ should not be greater than $w_{i}$.
iii) Joël then does the same for all the remaining edges.
iv) Joël wins if the number of coins on each vertex $v_{i}$ is equal to $w_{i}$.
Determine all graphs $G$ for which Joël has a winning strategy.