Caesar and BrutusGames
Two commanders (Caesar and Brutus) conquer a country which forms a connected graph with nodes representing cities and edges representing roads. First, Caesar chooses a city and claims it. Then, Brutus claims any of the remaining cities. Turn by turn, the commanders claim the available cities that are adjacent to the cities they have already claimed. If a commander cannot make a claim, he skips a move. The game continues until all cities have been claimed. Both commanders wish to claim a maximal number of cities. Can Brutus win in this game?