# Prove that a graph with at least one edge and all vertices of even degree must contain a cycle.

Whilst studying eulerian graphs I came across the problem:

Problem Prove that a graph $G$ with at least one edge and all vertices of even degree must contain a cycle.

My attempt: If $G$ is connected, then by definition it would be an Eulerian graph (Eulerian graphs are connected with even degree), and so it would have a cycle. Now suppose that $G$ is not connected, then choose some connected component $H_1 \subset G$ where that the edge set has cardinality greater than or equal to $1$ , which exists since $G$ has at least one edge. Then this graph is connected with vertices of even degree, and so is eulerian, and hence it has a cycle.

Is this reasoning correct?

Edit: My reasoning is NOT correct since what I showed is that there is an Euler tour which is not a cycle but a closed trail for anyone reading this in the future..

• Seems too easy to use facts about Eulerian graphs. I bet it's intended that you solve the problem from first principles, that is, without using anything about Eulerian graphs. – Gerry Myerson Feb 26 '17 at 8:31

Your reasnoning is correct, but there is much more simple one. Let start with vertex $v_0$ incident to at least one edge. Then we go to any adjacent vertex $v_1$. It has at least two incident edges, so we choose another edge to go to a non-visited vertex $v_2$. Repeating this process we always go a vertex different from previous one. But if graph has the finite number of vertices, then once we should go from vertex $v_j$ to vertex $v_i$ that was visited earlier. Then $v_iv_{i+1}\ldots v_{j-1}v_jv_i$ is a cycle. Also it is easy to see that graph with infinite number of vertices of even degree may have no cycle.