Metamath Proof Explorer


Table of Contents - 16.4.1. Eulerian paths

According to Wikipedia ("Eulerian path", 9-Mar-2021, https://en.wikipedia.org/wiki/Eulerian_path): "In graph theory, an Eulerian trail (or Eulerian path) is a trail in a finite graph that visits every edge exactly once (allowing for revisiting vertices). Similarly, an Eulerian circuit or Eulerian cycle is an Eulerian trail that starts and ends on the same vertex. ... The term Eulerian graph has two common meanings in graph theory. One meaning is a graph with an Eulerian circuit, and the other is a graph with every vertex of even degree. These definitions coincide for connected graphs. ... A graph that has an Eulerian trail but not an Eulerian circuit is called semi-Eulerian."

Correspondingly, an Eulerian path is defined as "a trail containing all edges" (see definition in [Bollobas] p. 16) in df-eupth resp. iseupth. is the set of all Eulerian paths in graph , see eupths. An Eulerian circuit (called Euler tour in the definition in [Diestel] p. 22) is "a circuit in a graph containing all the edges" (see definition in [Bollobas] p. 16), or, with other words, a circuit which is an Eulerian path. The function mapping a graph to the set of its Eulerian paths is defined as in df-eupth, whereas there is no explicit definition for Eulerian circuits (yet): The statement " is an Eulerian circuit" is formally expressed by .

Each Eulerian path can be made an Eulerian circuit by adding an edge which connects the endpoints of the Eulerian path (see eupth2eucrct). Vice versa, removing one edge from a graph with an Eulerian circuit results in a graph with an Eulerian path, see eucrct2eupth.

An Eulerian path does not have to be a path in the meaning of definition df-pths, because it may traverse some vertices more than once. Therefore, "Eulerian trail" would be a more appropriate name.

The main result of this section is (one direction of) Euler's Theorem: "A non-trivial connected graph has an Euler[ian] circuit iff each vertex has even degree." (see part 1 of theorem 12 in [Bollobas] p. 16 and theorem 1.8.1 in [Diestel] p. 22) or, expressed with Eulerian paths: "A connected graph has an Euler[ian] trail from a vertex x to a vertex y (not equal with x) iff x and y are the only vertices of odd degree." (see part 2 of theorem 12 in [Bollobas] p. 17). In eulerpath, it is shown that a pseudograph with an Eulerian path has either zero or two vertices of odd degree, and eulercrct shows that a pseudograph with an Eulerian circuit has only vertices of even degree.

  1. ceupth
  2. df-eupth
  3. releupth
  4. eupths
  5. iseupth
  6. iseupthf1o
  7. eupthi
  8. eupthf1o
  9. eupthfi
  10. eupthseg
  11. upgriseupth
  12. upgreupthi
  13. upgreupthseg
  14. eupthcl
  15. eupthistrl
  16. eupthiswlk
  17. eupthpf
  18. eupth0
  19. eupthres
  20. eupthp1
  21. eupth2eucrct
  22. eupth2lem1
  23. eupth2lem2
  24. trlsegvdeglem1
  25. trlsegvdeglem2
  26. trlsegvdeglem3
  27. trlsegvdeglem4
  28. trlsegvdeglem5
  29. trlsegvdeglem6
  30. trlsegvdeglem7
  31. trlsegvdeg
  32. eupth2lem3lem1
  33. eupth2lem3lem2
  34. eupth2lem3lem3
  35. eupth2lem3lem4
  36. eupth2lem3lem5
  37. eupth2lem3lem6
  38. eupth2lem3lem7
  39. eupthvdres
  40. eupth2lem3
  41. eupth2lemb
  42. eupth2lems
  43. eupth2
  44. eulerpathpr
  45. eulerpath
  46. eulercrct
  47. eucrctshift
  48. eucrct2eupth1
  49. eucrct2eupth