Question

a) Prove or disprove that all trees whose edges form a single path are graceful.

b) prove or disprove that all caterpillars are graceful.

Short answer

a) Therefore, proved that all trees whose edges form a single path are graceful.

b) Hence, proved that all caterpillars are graceful.

Step-by-step solution

General form

Definition of tree: A tree is a connected undirected graph with no simple circuits.

Definition of Circuit: It is a path that begins and ends in the same vertex.

Definition of Caterpillar: A caterpillar is a tree that contains a simple path such that every vertex not contained in this path is adjacent to a vertex in the path.

Definition of Graceful: A tree with n vertices is called graceful if its vertices can be labelled with the integers\({\bf{1,2,}}...{\bf{,n}}\) such that the absolute values of the difference of the labels of adjacent vertices are all different.

(a) Proof of the given statement

Given that, a tree T whose edges form a single path.

To prove: T is graceful

Proof:

Let T contain n vertices.

Then, we name the first vertex as 1, the third vertex as 2, the fifth vertex as 3, and so on. Until a vertex named as \(\left\lceil {\frac{{\bf{n}}}{{\bf{2}}}} \right\rceil \).

Next, we name the second vertex as n, the fourth vertex as\(n - 1\), the sixth vertex as \(n - 2\), and soon. Until a vertex named as \(\left\lceil {\frac{n}{2}} \right\rceil + 1\).

So, we noticed that the successive differences in the tree T are \(n - 1,n - 2,...,2,1\) and the difference of the labels of adjacent vertices are all different.

Conclusion: So, T is graceful.

(b) Proof of the given statement 

Given that, a caterpillar.

Let us name it as C.

To prove: C is graceful.

Proof:

Let C contain n vertices and let the longest path in C contain k vertices.

We can call this longest path as spine and all other vertices as feet.

Referring part (a) of the labelling.

Since, we label the first vertex in the spine with 1 and the adjacent vertex in the spine with n.

All feet of the vertex labelled n are labelled as \(2,3,...,m\)before we label the next vertex in the spine with\(m + 1\).

Next, we label all the feet of the vertex as \(m + 1\)by \(n - 1,n - 2,...,p\) and the next vertex in the spine with \(p - 1\).

And so on for all the other vertices of the spine.

So, we noticed that the successive differences in the tree C are\(n - 1,n - 2,...,2,1\) and the difference of the labels of adjacent vertices are all different.

So, C is graceful.

Hence proved.