Draw a graph so that between any pair of vertices, there are at least 4 paths.
Two paths linking the same pair of vertices must not share ANY edge.

Is it always possible to color the edges in two colors (say, red and black) so that between any pair of vertices, there are two red paths and two black paths ? (The two red paths must not have any edge in common, neither must the black paths).

At first i thought that this must obviously be true but (pic related) now i'm confused. It seems that it's not that easy to find a good coloration.
And even supposing it's true, i wouldn't know how to prove it.
Any idea ?