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.