I'm working on a homework and I know this:
- Initial state: I have a bidirectional graph G=(V,E) and from every vertex I can reach every other vertex – so I have a path between any two vertices.
- Final state: If I made my graph unidirectional, I have to keep it connected – I also mean that from every vertex I can reach every other vertex.
In the end, I have to show that this is possible if and only if in my initial state deleting a direction of an arrow doesn’t disconnect the network.
In order to reach my demonstration, I know that I have to show that any 2 vertices in G are connected by at least two edge-disjoint paths. Basically, I understand that I can't go back once I've deleted a "direction" of an edge. Also, then I can only get from that vertex over to the other side if deleting that edge wouldn't have disconnected the network.
So I think that I understand the idea of my problem, but I don't know how to write a real proof in order to show that any 2 vertices in G are connected by at least two edge-disjoint paths.
Best Answer
Does a bidirected graph include extraverted edges? Because then it would not be the case for a graph consisting of two vertices connected by an extraverted edge, right?
So in case each edge can only point in one of the two directions. We assume to graph is connected which means that for every $u,v \in V$, there is a path from u to v, and also a path from v to u.
If these paths are disjoint we are done. In case they are not, they intersect in some path $x_0x_1$ (or more than one). Note that this path is strictly smaller then |uv|. Note that because $x_0x_1$ is in only one direction, there exists a path $x_1x_0$, which intersect with $x_0x_1$ on stricly less edges than $|x_1x_0|$.
Thus for each intersection between two vertices, we can find some other path that intersects with strictly less edges than the original two paths. We can repeat in this manner and will reach in a finite amount of steps two paths that intersect in 0 edges.
Hope I understand your question correctly, good luck.