How to tell if an edge is on some path

Question

Given an undirected graph G=V,E, 2 vertices: x, y and an edge e,

I would like to check if there is a path from x to y that contains the given edge e.

What I thought: Solve this by defining a network flow where x and y are source and sink and check if the flow in e is more than 0 it means that there is a path. BUT there are 2 problems:

1. I don't know how to direct to edges
2. What would be the capacity of every edge?

So I'm guessing it's not the right approach... If someone can give an idea it'd be great.

Answer 1

One approach could be the following:

1. Remove the edge e = (u,v) from E(G).
2. If any x-y path contains e then the path will either be one of the two following forms: (1) x *-> u -> v *-> y or (2) x *-> v -> u *-> y where *-> means reachable. Use this fact to check if either of the following cases holds true 2.1. x is reachable from u and y is reachable from v. 2.2. x is reachable from v and y is reachable from u. We can use BFS to find reachablility.