Hint on homework 2

Some student asked me hint for problem 2 of homework 2.  The suggestion is that prove your claim with simple examples. For example, can you prove you claim on trees of size 3?