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.



  • 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$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.