My purpose is to understand if in a graph $G = \langle V, E\rangle$ given 4 vertices in input (a, b ,c and d) they belong to an infinite path. With infinite path I mean a vertex succession that has a known head without ending.


In other words what I'm trying to do is to find and algorithm that could identify this kind of sequence:


$$
p = a , x\_1 , x\_2 , x\_3, ... , c , ... , d , ... , b , x\_i , ...
$$


Before ask a question I've thought about using BFS because I have a sort of sequence to find, but I'm stuck at infinite path. I don't know how detect it.



Algorithm to check if vertex belong to infinite path in Graph theory
If there is an infinite path then there is also a finite path using two of $a,b,c,d$ as endpoints. However the converse is not true, so the question makes sense. There is some ambiguity about how explicitly one knows the graph. 


I will give a graph $H$ which is a disjoint union of paths and has an infinite path exactly if the [Collatz $3n+1$ conjecture](https://en.wikipedia.org/wiki/Collatz_conjecture) is false *due to an unbounded trajectory*. I will then make it into a tree $G$ (plus isolated vertices perhaps) by adding 4 more vertices $a,b,c,d$ which are in an infinite path exactly if $H$ has such a path. I am sure this is much more complicated than it needs to be, but it does work.


Define the function $f$ on positive integers by $f(n)=\frac{n}{2}$ for $n$ even and $f(n)=3n+1$ for $n$ odd. The conjecture is that iteration always arrives at $1.$ Equivalently, for all $n \gt 1$ there is in the list $n,f(n),f(f(n))=f^2(x),f^3(x), \cdots$ a number less than $n.$ If there is a counter-example $n,$ then it is odd and either the sequence above enters a cycle not including $1$ or is the start of a trajectory which increases without bound. It is this second case that would lead to an infinite path .


The vertices of the graph $H$ will be all integer points $(x,y)$ with $2 \leq x \leq y.$ The vast majority will turn out to be isolated points (for example those with $x$ even) so one might also consider generating paths as about to be defined and adding vertices as they arise.


From each point $(x,x),$ start a path $(x,x)=(x,f^0(x)),(x,f(x)),(x,f^2(x)),\cdots\ $ However stop at $(x,y)=(x,f^k(x))$ if it turns out that $f(y)=f^{k+1}(x) \lt x.$


Then this graph $H$ has an infinite path exactly if the conjecture is false. To get $G,$ add four vertices $a,b,c,d$ with edges $(a,b),(b,c),(c,d)$ and also add an edge from $d$ to each $(x,x).$ Then there is an infinite path in $G$ using $a,b,c,d$ exactly if $H$ has an infinite path.


In $G$ every vertex has degree $0,1$ or $2$ except that $d$ has infinite degree. There might be an easy variation which has all vertices of bounded (or at least finite) degree, however I could imagine that there isn't one. 


