Let $G$ be a simple, bridgeless (2-edge connected), undirected graph and let $P$ be an arbitrary path between vertices $u$ and $v$ of $G$. Will $u$ and $v$ be in the same component of $G \setminus P$?
Update: I had to recognize that removing $P$ can destroy the connection between $u$ and $v$. Let us consider the following 2-edge connected graph:
Indeed, there are two independent paths $u$ and $v$, whose edges are denoted with "1" and "2". Nevertheless, if $P$ is choosen such that their edges would be the red ones, then there is not another $Q$ path independent of $P$. Do you have any idea what to do in these cases?
Best Answer
Apologies for the original error in not spotting the counterexample! The problem seems to be that, in removing a path, you create a graph with a bridge in the process. What I said about 2-connected bridgeless graphs being a union of subcomponents that are cycle graphs seems to make sense - a cycle graph is the minimal example of this type of graph and if you add edges then it does not change this property. You can add more cycles through shared vertices and edges of existing property and this property still does not change. Where the problem occurs in the counterexample is that we have one shared edge and two shared vertices between two 4-cycles, but you can easily see how that can be extended more generally to cause a problem.
The minimum number of edges in a simple connected graph on n nodes is n-1 (a tree). Note that removing the path in the counterexample brings the number of edges below this number and so we must be creating disjoint graphs somewhere in the process! This holds true for any graph, so if we are removing a path between u and v and the total number of edges falls below n-1, then we should check to see that u and v are not in disjoint graph components. The opposite does not generally hold true - if a graph has more than n-1 edges is not necessarily connected. That is easy to see if you connect a sufficiently large complete graph onto the far end of one of the sides of your example - the path still disconnects u and v even though it can have a lot more than n-1 edges. I just mean to say that this cannot be the basis of a test to see if u and v are still connected.
If you want to find two paths between u and v such that removing either one does not leave u and v disconnected, you should probably look into a cycle detection algorithm for undirected graphs for finding a cycle - preferably minimal - that contains both u and v. Removing both paths and keeping u and v connected is impossible without stronger restrictions on the type of graph if you consider the cycle example.