Find edges part of a simple path between two vertices Suppose G is an undirected graph. How can I efficiently find all edges in G that are part of a simple path between given vertices A and B?
 A: Let $a,b \in V(G)$, and $e \in E(G)$. Then $e$ is on some path from $a$ to $b$ in $G$ if and only if $a$, $b$, and $e$ are in the same component in $G$ and $e$ is in a biconnected component that is on the unique path from the biconnected component containing $a$ to the biconnected component containing $b$ in the block tree for $G$. 
Proof: Suppose $a$, $b$, and $e$ are in the same component in $G$ and $e$ is in a biconnected component $B_e$ that is on the unique path from the biconnected component $B_a$ containing $a$ to the biconnected component $B_b$ containing $b$ in the block tree for $G$. If $B_a \neq B_e$, find a path $P_a$ in $G$ internally disjoint from $B_e$ from $a$ to a vertex $a'$ in $B_e$. If $B_a = B_e$, let $a' = a$, and $P_a = a$. Similarly, if $B_b \neq B_e$, find a path $P_b$ in $G$ internally disjoint from $B_e$ from $b$ to a vertex $b'$ in $B_e$. If $B_b = B_e$, let $b' = b$, and $P_b = b$. Now if $e = a'b'$, then $P_a \cup e \cup P_b$ is a path from $a$ to $b$ in $G$. If $e$ is incident with $a'$ or $b'$, then by Menger's theorem find two disjoint paths in $B_e$ from the ends of $e$ to whichever of $a'$ or $b'$ is not incident with $e$, then one of these paths together with $e$, $P_a$ and $P_b$ is a path from $a$ to $b$ containing $e$. Finally, if neither $a'$ nor $b'$ are ends of $e$, by Menger's Theorem, there are two disjoint paths in $B_e$ from $a'$ and $b'$ to the ends of $e$, and these two paths together with $e$, $P_a$ and $P_b$ is a path from $a$ to $b$ containing $e$. 
Conversely, if $e$ is not in the same component as $a$ and $b$, clearly there is no path from $a$ to $b$ containing $e$, and if $B_e$ is not on the path in the block tree for $G$ from $B_a$ to $B_b$, there cannot be a path from $a$ to $e$ that is disjoint from a path from $b$ to $e$, and hence there cannot be a path from $a$ to $b$ containing $e$. $\Box$
See, for example, this for definitions, and also an algorithm that determines biconnected components in linear time. Using this result and that algorithm, it should be possible to find all such edges in linear time.
