Question: Given an undirected graph `G = (V, E)`, such that `u`, `v`, `w` are some edges in G.

Describe an algorithm to determine whether

*"if there is a path from u to w that passes through v"*

A simple algorithm for that using DFS is given below:

```
bool checkFunction(){

  graph g; // containing u, w, v
  dfs(v);

  if(isVisited(u) && isVisited(w))
    return true;
  else
    return false;

}

```

For the above algorithm,

* time complexity : O(V+E)
* space complexity : O(V)

But can we reduce the time complexity?

Answer: 
**Note:** This post doesn't provide a solution to the question posted, but it does provide some information regarding common mistakes one can make while solving such problems.

(This post also assumes paths to not allow duplicate vertices. If you remove this constraint, the problem can be solved easily by finding a path from u to v, and a path from v to w and just concatenating these 2 paths to get a [walk](https://en.wikipedia.org/wiki/Path_(graph_theory)#Walk,_trail,_path) from u to w passing through v. This can be achieved by running BFS once from u and once from v)

The [answer given by amit](https://stackoverflow.com/a/62744121/102937) isn't correct.

---

**Edit:**  

The below counter example is incorrect, see the comment by Steve. I have provided another counter example after this one.  

Consider a counter example.  

V = {u, v, w, x}  

E = {{u,v}, {u,w}, {u,x}, {v,x}, {w,x}}  

Then, the path (u,v,x,w) is a valid path.  

Now lets say we apply BFS on w, the corresponding paths (not unique) we get from w to u and w to v will be (w,u) and (w, u, v)  

Now, the "path" (v,u,w,u) has a repeated node u, so it's not a path.

---

Another counter example:  

Consider V = {u,v,w,x,y,z} E = {{u,x}, {v,x}, {x,w}, {v,y}, {y,z}, {z,w}}  

A BFS Tree from w will have the edges {{w,x}, {w,z}, {x,u}, {x,v}} (we treat u,v as sinks)  

This gives the "path" {u,x,w,x,v} which is invalid

The [answer by Matt](https://stackoverflow.com/a/62744090/102937) is also incorrect.

> 
> A path exists iff u, v, and w are in the same connected component.
> 
> 
> 

Consider a line graph {w, u, v}, then all these 3 lie in the same connected component, but there is no path from u to w that passes through v

---

This problem (for undirected graphs) is also stated [here](https://algs4.cs.princeton.edu/64maxflow/) (See problem 7), which I think is a reputable source, so we can safely assume that there does exist an efficient algorithm for this.  

[This](https://cstheory.stackexchange.com/questions/20185/subgraph-containing-all-nodes-and-edges-that-are-part-of-length-limited-simple-s/21809) also argues for the existence of a solution, as well as provides an algorithm.  

For directed graphs, this is a ["hard" problem](https://cstheory.stackexchange.com/questions/20137/subgraph-containing-all-nodes-and-edges-that-are-part-of-length-limited-simple-s).
Do a BFS starting from `u`. Stop it when you find `v`.

Now, do a BFS from `v`. Stop it when you find `w` and return `true`.

If you don't find `v` in the first BFS or `w` in the second BFS, it means there is no path from `u` to `w` passing through `v` and you can stop the prodecure returning `false`.

Complexity: O(|V| + |E|)