December2015 Cs Q5

0. A tree with n vertices is called graceful, if its vertices can be labelled with integers 1, 2, ...,n such that the absolute value of the difference of the labels of adjacent vertices are all different. Which of the following trees are graceful?

Answer
Comment
Array

Option : D
Explanation :
Caterpillar tree: In graph theory, a caterpillar is a tree in which all the vertices are within distance 1 of a central path.
Theorem: All caterpillars are graceful.
So, (a), (b) and (c) are graceful.

Forgot your password?

I agree with the Terms.