Assume there is a graph $G = (V, E)$ and a hash function $H: V^n \rightarrow \{0,1\}^m$. Given a path $p = (v_1, v_2, ..., v_n)$ from the graph $G$, compute its hash value $H(p) = h_p$.
Question: Given only the value $h_p$ for any path in the graph (or any "non-path" in the graph), can one prove or disprove that the path exists in the graph?
Possible solution: Expand the graph $G$ into a (possibly) infinite Merkle tree considering every vertex in $V$ as the respective root of the tree (designate these $m_v$). Try to match the hash value $h_p$ with all of the $m_v$ trees. If at least one tree can authenticate the $h_p$ value, then the path exists.
Remark: A non-path would be a sequence of vertices that does not correspond to the edges in the graph.
If it is a finite graph, the answer is yes, because for fixed $n$ there is only a finite number of paths of length $n$ in the graph. For example, you can enumerate all $n$-tuples of distinct vertices in the graph, check whether they form a path, compute the hash value of that path if they do, and check if that hash occurs in your list of hashes.