# Connectivity in a graph with even-degree vertices is preserved by edge removal

I was wondering if I could get some help with this proof.

Essentially, I have to prove that when you have a connected graph with each vertex being of even degree (at least 2) and it is possible to go from any vertex to another through some path, if you remove an edge, it is still possible to go from any vertex to another. I was thinking of using induction on number of edges, but I'm having trouble considering that once you remove an edge, the two vertices between the edge each lose a degree and no longer are of even degree.

• Your statements are incorrect I think. You want to show that if ever vertex has even degree, there is a path that uses every edge exactly once from that starts and stops on the same vertex. If you remove one edge (so that you have exactly two vertices of odd degree), then you can still find a path that uses every edge exactly once, but it does not start and stop at the same vertex. Such graphs are called Eulerian. If you really just want to show that you can travel from any vertex to any other, this follows from connectivity and has nothing to do with every vertex having even degree. Commented Nov 4, 2018 at 5:31