Algorithm for Longest Path in Undirected Weighted Graph
Two questions where I think you have remained unclear:


Are there any assumptions on the weight function?
What exactly holds if $(x, y) \in R$?


Ad 4: You break your desired invariant for $R$ here since the last node in $x$ does not necessarily occur in $w$ at all. Example: $x = abc, y=adc, z=adce, w=ae$

I believe a worst-case instance might be the complete graph with $w(i,k) = 1$ for $i$ the starting node and all $k\neq i$, and $w(j, k) = 0$ for all $j,k \neq i$. Paths with more nodes will never remove those from earlier iterations so the tree is never shrunk at all, growing up to having $n!$ nodes.