Constructing a path of a fixed finite length

Question

Fix an index set $I=\{1,\dots,n\}$ and a set of indexed labels $L= \{a_1,a_2,\dots,a_n,b_1,b_2,\dots,b_n\}$. Let $G=(V,E,f)$ be a vertex-labeled graph, where $f: L \to \mathscr{P}(V)$ is a labeling function assigning to each label $\ell\in L$ a set of vertices $f(\ell)$, and such that $E$ is given by:

$(v,v')\in E \iff \exists i\in I \text{ s.t. } v\in f(a_i) \text{ and } v'\in f(b_i)$

Suppose there is a path $P=v_1v_2\dots v_m$ for finite $m$ with $m>n+1$. I'd like to show that there is another path $P'=u_1u_2\dots u_p$ with $u_1=v_1$, $u_p=v_m$ with length at most $n+1$.

My attempt so far is to construct $P'$ as follows. Given the structure of $P$, we know that, for each $j\in \{1,\dots,m-1\}$, there is some $i\in I$ such that $v_j\in f(a_i)$ and $v_{j+1}\in f(b_i)$. Let us denote the labels ''responsible'' for the the existence of edge $(v_j,v_{j+1})$ along $P$ by $a_{i_j}$ and $b_{i_j}$.

To construct $P'$, set $u_1=v_1$. Now set $u_2 = \max_{1\leq j\leq m}\{v_j \mid v_j\in b_{i_1}\}$. If $u_2=v_m$, i.e., if $b_{i_1}=b_{i_{m-1}}$ we are done. Otherwise, we have $u_2=v_k$ for some $k<m$. And as we have $(v_k,v_{k+1})$ along $P$ and $v_k = \max_{1\leq j\leq m}\{v_j \mid v_j\in b_{i_1}\}$, we get $a_{i_k}\neq a_{i_1}$ and $b_{i_k}\neq b_{i_1}$. Set $u_3 = \max_{1\leq j\leq m}\{v_j \mid v_j\in b_{i_k}\}$. If $u_3=v_m$, we are done. Otherwise we repeat this process until we obtain the desired path $P'$.

I would be grateful if anyone could give me some advice on how to turn this into a rigorous proof (or point to a mistake otherwise).

Thanks for the help.

Answer 1

Hint:

• As you have noted, for each edge, there is a label responsible for existence of that edge.
• There are only $n$ labels, but $P$ has $m-1 > n$ edges, so some label has to be used twice.
• Let $(v_1, v_2)$ and $(v_3, v_4)$ be two edges (not necessarily consecutive) that use the same label. Then, $(v_1, v_4)$ and $(v_3, v_2)$ are also valid edges.

I hope this helps $\ddot\smile$