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..
Best Answer
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 the previous one. But if graph has a 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.
Edit. I state that original reasoning is correct (for a finite graph) though imcomplete. Graph induced by a closed trail is always a union of several pairwise edge-disjoint simple cycles.