# Foremost Walks and Paths in Interval Temporal Graphs +
## 4 Min-Hop Foremost Paths  
Before we develop the algorithm for finding \(mhf\) paths in interval-temporal graphs, we present the following theorems about \(mhf\) paths in temporal graphs.  
**Theorem 3**.: _There exist interval-temporal graphs in which every \(mhf\) path from a source vertex \(v\) to a destination vertex \(v\) has a prefix-path ending at a prefix vertex \(u\) and the prefix-path from \(s\) to \(u\) is not a min \(-\) hop path._  
Proof.: This can be seen from Figure 7. The only \(mhf\) path from \(a\) to \(d\) is \(<a,0,b,1,c,2,d>\). However, the prefix path \(<a,0,b,1,c>\) is not a min-hop path from \(a\) to \(c\). The min-hop path from \(a\) to \(c\) is \(<a,8,c>\) which is not a prefix path to the only \(mhf\) path from \(a\) to \(d\), even though this \(mhf\) path goes via \(c\).  
**Theorem 4**.: _There exist interval-temporal graphs in which every \(mhf\) path from a source vertex \(v\) to a destination vertex \(v\) has a prefix path ending at a prefix vertex \(u\) and the prefix path from \(s\) to \(u\) is not a foremost path._  
Proof.: This can also be seen from Figure 7. The only \(mhf\) path from \(a\) to \(f\) is \(<a,0,b,7,d,8,f>\). However the prefix path \(<a,0,b,7,d>\) is not a foremost path from \(a\) to \(d\). There are two foremost paths from \(a\) to \(d\) in the interval-temporal graph of Figure 7, namely, \(<a,0,b,1,c,2,d>\) and \(<a,0,b,1,c,2,e,3,d>\). Neither of these foremost paths from \(a\) to \(d\) is a prefix path to the only \(mhf\) path from \(a\) to \(f\), even though this \(mhf\) path goes via \(d\).  
**Theorem 5**.: _There exist interval-temporal graphs in which every \(mhf\) path from a source vertex \(v\) to a destination vertex \(v\) has a prefix path ending at a prefix vertex \(u\) and the prefix path from \(s\) to \(u\) is not an \(mhf\) path._  
Proof.: This can also be seen from Figure 7. The \(mhf\) path from \(a\) to \(f\) is \(<a,0,b,7,d,8,f>\). However, the prefix path \(<a,0,b,7,d>\) is not an \(mhf\) path from \(a\) to \(d\). Out of the two foremost paths from \(a\) to \(d\) in the interval-temporal graph of Figure 7, namely, \(<a,0,b,1,c,2,d>\) and \(<a,0,b,1,c,2,e,3,d>\), the former has a fewer number of hops. Therefore, it is the the \(mhf\) path from \(a\) to \(d\). However, it is not a prefix path for the only \(mhf\) path from \(a\) to \(f\), even though the only \(mhf\) path from \(a\) to \(f\) goes via \(d\).  
**Theorem 6**.: _Consider an interval graph \(G\) that has a path from \(s\) to \(v\). \(G\) has an \(mhf\) path \(P\) from \(s\) to \(v\) with the property that every prefix \(Q\) of \(P\) is an \(h\) hop foremost path to \(u\), where \(h\) is the number of hops in \(Q\) and \(u\) is the last vertex of \(Q\)._  
Proof.: Since \(G\) has a path from \(s\) to \(v\), it has a min-hop foremost path \(R\) from \(s\) to \(v\). Let \(S\) be the longest prefix of \(R\) that is not an \(h\)-hop foremost path from \(s\) to \(u\), where \(h\) is the number of hops in \(S\) and \(u\) is the last vertex in \(S\). If there is no such \(S\) then the theorem is proved. Assume \(S\) exists. Replace \(S\) in \(R\), by an \(h\)-hop foremost path from \(s\) to \(u\), say \(S^{\prime}\). The resulting path \(R^{\prime}\) is an \(mhf\) path from \(s\) to \(v\) with a prefix \(S^{\prime}\) from \(s\) to \(u\) with an earlier arrival time at \(u\), but the same number of hops. Repeating this replacement strategy a finite number of times, we obtain a min-hop foremost path \(P\) from \(s\) to \(v\) that satisfies the theorem.