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$
  • 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$ – Yuval Filmus Oct 11 '16 at 15:12
  • 3
    $\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 Nov 13 '16 at 10:10

Your Answer

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

Browse other questions tagged or ask your own question.