0
$\begingroup$

Recently, I am reading the book [1]. I am trying to solve the following problem:

1.3 Proving Euler's claim. Euler didn't actually prove that having vertices with even degree is sufficient for a connected graph to be Eulerian--he simply stated that it is obvious. This lack of rigor was common among 18th century mathematicians. The first real proof was given by Carl Hierholzer more than 100 years later. To reconstruct it, first show that if every vertex has even degree, we can cover the graph with a set of cycles such that every edge appears exactly once. Then consider combining cycles with moves like those in Figure 1.8. Combining cycles at a crossing.


The following is my attempt to solve the problem:

Let $G$ be a connected graph and every vertex of $G$ has even degree. Let $N_V$ be the number of vertices in $G$. Let $d_i$ be the degree of the $i$th vertex for $i = 1, ..., N_V$. Then $$ d_i = 2 n_i \tag{1} $$ for some positive integer $n_i$, $i = 1, ..., N_V$. Therefore, by walking on the edges of $G$, we can walk to and leave the $i$th vertex for $n_i$ times, with each edge being walked on exactly once. Then I don't know how to continue...

I also go to the Internet and find Carl Hierholzer's paper [2]. However, it is written neither in English nor Chinese (my mother language), so I can't read it.

Note: It is not my homework. I am just interested in solving this problem.

References

[1] C. Moore and S. Mertens, The Nature of Computation, Oxford University Press, 2015.

[2] C. Hierholzer. Ueber die Möglichkeit, einen Linienzug ohne Wiederholung und ohne Unterbrechung zu umfahren. Mathematische Annalen, 6:30-32, 1873.

$\endgroup$
2
  • 1
    $\begingroup$ There is a lot of information on this topic on the web and in textbooks. Here are lecture notes by Ethan Kim, for example. $\endgroup$ Commented Oct 11, 2016 at 15:12
  • 4
    $\begingroup$ I'm voting to close this question as off-topic because it has little to do with computer science. Perhaps it should be asked on Mathematics instead. $\endgroup$
    – Juho
    Commented Nov 13, 2016 at 10:10

1 Answer 1

1
$\begingroup$

I don't know German either, but here are some of my thoughts based on the hint given.

Case 1: all vertices have even degree.

Take an arbitrary cycle and remove it. In the new graph (not necessarily connected) all the vertices will still have even degree. Repeat this process until all the edges have been eliminated. Glue all the cycles in the way described in the book.

It might not be apparent that such a cycle would exist for any graph in case 1. So we can prove it by contradiction. If the converse was true, there would exist a vertex such that no cycle can pass through it. This would imply that if we cut off one edge that connects such vertex, the new graph would no longer be connected, which is not true given the assumption that every vertex has even degree.

Case 2: Exactly two vertices have odd degree. Find a path connecting the two vertices and remove it, and we are back to case 1.

$\endgroup$
1
  • $\begingroup$ Thank you very much for answering my question. $\endgroup$ Commented Sep 13, 2021 at 7:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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