Share
Explore BrainMass

Graceful Trees and Paths

A (p,q) graph G is called graceful if it is possible to label the vertices of G with distinct
elements from the set {0,1,...,q} in such a way that the induced edge labeling, which
assigns the integer |i - j| to the edge ij, assigns the labels 1,2,...,q to the q edges of G.
The graceful tree conjecture states that every tree is graceful.
a. Prove that every path is graceful.
b. Prove that every star K_(1,n) is graceful.
c. Show that every tree of order 6 is graceful.

Solution Preview

There are some typos in the statement.
Here is a corrected text:
============================
A (p,q) graph G is called graceful if it is possible to label the vertices of G with distinct
elements from the set {0,1,...,p} in such a way that the induced edge labeling, which
assigns the integer |i - j| to the edge ij, assigns the labels 1,2,...,q to the q edges of G.
The ...

Solution Summary

Graceful trees and paths are investigated. The solution is detailed and well presented. The response received a rating of "5/5" from the student who originally posted the question.

$2.19