# Suppose G is a connected graph in which each vertex has even degree. Then, G has no cut edges.

I tried to prove this statement by contradiction, where G is a connected graph in which each vertex has even degree and G has a cut edge, then proceed letting x, y, z to be in G where x, y are endpoints to the cut edge e. So x and y are in two separate component of G - e. Then I tried to show that there is a path from x to z and one from y to z, so x and y must not be in two components. Therefore there is a contradiction. But I don't know if the proof is valid and how to best utilize the fact that the vertices have even degrees?

• How did you show that there is a path from x to z and a path from y to z? This doesn't immediately sound easy? The easiest way (IMO) to prove this result is to observe that x and y each have odd degree once e is deleted. Then if x and y are in the same component, contradiction e was not a cut edge, whereas if x and y are in different components, then the degree sum of each component is odd, contradiction by handshake lemma. Commented Dec 20, 2021 at 3:59

HINT: if there is a cut edge $$e$$, then each of the 2 components of $$G\setminus \{e\}$$ has exactly $$1$$ vertex of odd degree. The Handshake Lemma has something to say about this though.
Let's take an arbitrary edge $$e$$ and study whether it's a cut edge. We will take its end points $$v, w$$, and see if there is a path from one to the other that doesn't use $$e$$.
The graph has an Eulerian cycle. Take such a cycle that starts at $$v$$. Either this cycle gets to $$w$$ before it traverses $$e$$, or its reverse does. Either way, deleting $$e$$ does not disconnect the graph.