MathDB

Given a (simple) graph

G

with

n \geq 2

vertices

v_1, v_2, \dots, v_n

and

m \geq 1

edges, Joël and Robert play the following game with

m

coins:
[*]Joël first assigns to each vertex

v_i

a non-negative integer

w_i

such that

w_1+\cdots+w_n=m

. [*]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

. [*]Joël then does the same for all the remaining edges. [*]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.

Problem Statement