Hint for Exercise 7.27, part 1.
Instead of using either Hamiltonian Path or X3C, use 3SAT.
Use a construction similar to that in Figure 7.4 (on p. 237).
Differences are:
* use a single vertex for each clause
* add a "tail" of 2 edges to the topmost vertex ("root")
* the lengths (weights) of edges are:
- from root to literal vertices is 2
- between literals is 1
- coming out of clause vertices is 3
Set diameter bound to 4 and total weight bound to 3(n+m),
where n is the number of variables and m is the number of clauses.