If you study the result you should notice that it is correctly translating verticies ...,3,5,... but not translating verticies ...,5,3,... Within the graph functions provided by Mathematica it understands your edges are undirected. But the simple pattern matching that I showed did not consider this. Try this on your paths
edgerule = {1 <-> 2 -> A, 2 <-> 3 -> B, 3 <-> 4 -> C, 4 <-> 5 -> D, 2 <-> 6 -> E, 4 <-> 6 -> F, 5 <-> 7 -> H, 6 <-> 7 -> I,
2 <-> 8 -> J, 6 <-> 9 -> K, 7 <-> 10 -> L, 8 <-> 9 -> M, 8 <-> 11 -> N, 9 <-> 10 -> O, 9 <-> 12 -> P, 10 <-> 13 -> Q,
11 <-> 12 -> R, 11 <-> 14 -> S, 11 <-> 15 -> T, 12 <-> 13 -> U, 13 <-> 14 -> V, 14 <-> 15 -> W} /. UndirectedEdge -> List;
edgerule = Flatten[edgerule /. Rule[List[h_, t_], l_] -> {Rule[List[h, t], l], Rule[List[t, h], l]}];
That expands your edgerule to include paths going in either direction between two verticies. Then
Map[Partition[#, 2, 1] &, ...yourvertexsolution...]/. edgerule
should give you the solution labeled as you desire.
Study the details of this method carefully until you can fully understand the ideas used. That will help you in the future.
