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$
  • 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$ – Gerry Myerson Feb 26 '17 at 8:31
3
$\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 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.

$\endgroup$
  • 1
    $\begingroup$ That's more like it. $\endgroup$ – Gerry Myerson Feb 27 '17 at 9:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.