1
$\begingroup$

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..

$\endgroup$
1
  • 3
    $\begingroup$ 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. $\endgroup$ Feb 26, 2017 at 8:31

1 Answer 1

4
$\begingroup$

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.

$\endgroup$
1
  • 1
    $\begingroup$ That's more like it. $\endgroup$ Feb 27, 2017 at 9:28

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .