Solution

ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2015/iii/paper-24/2/b/ii/solution

Let be the common-prefix index from the first-divergence lemma for minimal walks. If , the walk to has followed the entire walk to and must make at least one further step, contradicting the assumed equality of lengths. Hence .
The current nodes agree, so put . Then is an initial segment of . It is proper because . Therefore
In particular, each function is injective: equality of two trace sequences would give equal lengths and then contradict this proper-initial-segment conclusion.

New to topics? Read the docs here!