MathDB

n

people decide to play a game. There are n\minus{}1 ropes and each of its two ends are in hand of one of the players, in such a way that ropes and players form a tree. (Each person can hold more than rope end.) At each step a player gives one of the rope ends he is holding to another player. The goal is to make a path of length n\minus{}1 at the end. But the game regulations change before game starts. Everybody has to give one of his rope ends only two one of his neighbors. Let

a

and

b

be minimum steps for reaching to goal in these two games. Prove that a\equal{}b if and only if by removing all players with one rope end (leaves of the tree) the remaining people are on a path. (the remaining graph is a path.) http://i37.tinypic.com/2l9h1tv.png

Problem Statement