Let $G$ be a connected graph with the degree of all vertices being even. I want to prove that for any two vertices, $u$, $v$, there exist two paths between them with no common edges.
My attempt: if only one path exists between $u$ and $v$, then the edges along this path are bridges. If two paths exist between $u$ and $v$, but one of the edges of these two paths is the same, then this edge will be a bridge. Thus, proving that $G$ is bridgeless is sufficient. Assume that a bridge, $b$, does exist in $G$. Then we can write:
$$G-b=\tilde{G}_1\cup\tilde{G}_2$$
with $u\in\tilde{G}_1$ and $v\in\tilde{G}_2$. We know that the degree of all vertices in $\tilde{G}_1$ were even, but by removing the edge between $u$ and $v$, the degree of $u$ is now odd. Therefore, the sum of the degrees of all vertices in $\tilde{G}_1$ is odd, which is against the first theorem of graph theory. This shows by contradiction that $G$ is bridgeless and therefore (I believe) proves the statement in the top of the post.
Is my proof valid?
Best Answer
It is valid, but the existence of a bridge is not proved. Why does the fact that any two $st$-path intersects imply that there is a bridge? If you know Menger's theorem or max-flow min-cut, then that would complete your proof. Otherwise, there is still some work to do...