Minimum number of clicks to turn all the edges on.

Question

On clicking a node in a tree, all the adjacent edges are turned on. Calculate min of clicks such that all the edges are turned on.

Answer 1

Color your $n$ vertices with two colors such that any two adjacent vertices have different colors (this is possible because your graph is a tree, see bipartite graph). Now click on the vertices of the color you used less then all the edges will turn on. By the box-principle the number of such vertices is less or equal to $\lfloor n/2\rfloor$.

Note that for a star graph (which is a tree), it suffices to click on one vertex at the center, but in general the bound above can not be smaller because the linear graph (which is a tree) with $n$ vertices need at least $\lfloor n/2\rfloor$ clicks.