# Prove: A connected graph contains an Eulerian cycle iff every vertex has even degree

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.

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.

• There is a lot of information on this topic on the web and in textbooks. Here are lecture notes by Ethan Kim, for example. Commented Oct 11, 2016 at 15:12
• 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.
– Juho
Commented Nov 13, 2016 at 10:10
{"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 1, "mathjax_display_tex": 1, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0, "url": "https://cs.stackexchange.com/questions/64485/prove-a-connected-graph-contains-an-eulerian-cycle-iff-every-vertex-has-even-de", "fetch_time": 1719064499000000000, "content_mime_type": "text/html", "warc_filename": "crawl-data/CC-MAIN-2024-26/segments/1718198862396.85/warc/CC-MAIN-20240622112740-20240622142740-00106.warc.gz", "warc_record_offset": 164639532, "warc_record_length": 40053, "token_count": 536, "char_count": 2053, "score": 3.859375, "int_score": 4, "crawl": "CC-MAIN-2024-26", "snapshot_type": "latest", "language": "en", "language_score": 0.9386551976203918, "file_path": "/sailhome/yjruan/project/latent-lm/data/processed/finemath-4plus/finemath-4plus/train-00046-of-00064.parquet"}