This is a problem from Algorithms by Dasgupta, Papadimitriou, and Vazirani (problem 3.27):
Two paths in a graph are called edge-disjoint if they have no edges in common. Show that in any undirected graph, it is possible to pair up the vertices of odd degree and find paths between each such pair so that all these paths are edge-disjoint.
Maybe I'm interpreting the question wrong, but isn't this a valid counterexample?
All vertices have an odd degree (1 or 3), but the paths between all pairs are not disjoint..