Editing Eulerian path

{{Short description|Trail in a graph that visits each edge once}}
[[File:Comparison_7_bridges_of_Konigsberg_5_room_puzzle_graphs.svg|thumb|[[Multigraph]]s of both [[Seven Bridges of Königsberg|Königsberg Bridges]] and [[Five room puzzle]]s have more than two odd vertices (in orange), thus are not Eulerian and hence the puzzles have no solutions.]]
[[File:Labelled Eulergraph.svg|thumb|Every vertex of this graph has an even degree. Therefore, this is an Eulerian graph. Following the edges in alphabetical order gives an Eulerian circuit/cycle.]]
In [[graph theory]], an '''Eulerian trail''' (or '''Eulerian path''') is a [[trail (graph theory)|trail]] in a finite [[graph (discrete mathematics)|graph]] that visits every [[edge (graph theory)|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 (graph theory)|vertex]]. They were first discussed by [[Leonhard Euler]] while solving the famous [[Seven Bridges of Königsberg]] problem in 1736. The problem can be stated mathematically like this:

:Given the graph in the image, is it possible to construct a [[path (graph theory)|path]] (or a [[cycle (graph theory)|cycle]]; i.e., a path starting and ending on the same vertex) that visits each edge exactly once?

Euler [[mathematical proof|proved]] that a necessary condition for the existence of Eulerian circuits is that all vertices in the graph have an [[parity (mathematics)|even]] [[degree (graph theory)|degree]], and stated without proof that [[connectivity (graph theory)|connected graphs]] with all vertices of even degree have an Eulerian circuit. The first complete proof of this latter claim was published posthumously in 1873 by [[Carl Hierholzer]].<ref>N. L. Biggs, E. K. Lloyd and R. J. Wilson, ''[[Graph Theory, 1736–1936]]'', Clarendon Press, Oxford, 1976, 8–9, {{ISBN|0-19-853901-0}}.</ref> This is known as '''Euler's Theorem:'''

:A connected graph has an Euler cycle [[if and only if]] every vertex has an even number of incident edges.

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.<ref>{{cite journal |doi=10.1137/0128070 |author=C. L. Mallows, N. J. A. Sloane |title=Two-graphs, switching classes and Euler graphs are equal in number |journal=[[SIAM Journal on Applied Mathematics]] |volume=28 |year=1975 |pages=876–880 |jstor=2100368 |issue=4 |url=http://neilsloane.com/doc/MallowsSloane.pdf }}</ref>

For the existence of Eulerian trails it is necessary that zero or two vertices have an [[parity (mathematics)|odd]] degree; this means the Königsberg graph is ''not'' Eulerian. If there are no vertices of odd degree, all Eulerian trails are circuits. If there are exactly two vertices of odd degree, all Eulerian trails start at one of them and end at the other. A graph that has an Eulerian trail but not an Eulerian circuit is called '''semi-Eulerian'''.

==Definition==
An '''Eulerian trail''',<ref name="pathcycle" group="note">Some people reserve the terms ''path'' and ''cycle'' to mean ''non-self-intersecting'' path and cycle.  A (potentially) self-intersecting path is known as a '''trail''' or an '''open walk'''; and a (potentially) self-intersecting cycle, a '''circuit''' or a '''closed walk'''. This ambiguity can be avoided by using the terms Eulerian trail and Eulerian circuit when self-intersection is allowed.</ref>  or '''Euler walk''', in an [[undirected graph]] is a walk that uses each edge exactly once. If such a walk exists, the graph is called '''traversable''' or '''semi-eulerian'''.<ref>Jun-ichi Yamaguchi, [http://jwilson.coe.uga.edu/EMAT6680/Yamaguchi/emat6690/essay1/GT.html Introduction of Graph Theory].</ref>

An '''Eulerian cycle''',<ref name="pathcycle" group="note" /> also called an '''Eulerian circuit''' or '''Euler tour''', in an undirected graph is a [[cycle (graph theory)|cycle]] that uses each edge exactly once.  If such a cycle exists, the graph is called '''Eulerian''' or '''unicursal'''.<ref>Schaum's outline of theory and problems of graph theory By V. K. Balakrishnan [https://books.google.com/books?id=1NTPbSehvWsC&dq=unicursal&pg=PA60].</ref>  The term "Eulerian graph" is also sometimes used in a weaker sense to denote a graph where every vertex has even degree. For finite [[connected graph]]s the two definitions are equivalent, while a possibly unconnected graph is Eulerian in the weaker sense if and only if each connected component has an Eulerian cycle.

For [[directed graph]]s, "path" has to be replaced with ''[[directed path (graph theory)|directed path]]'' and "cycle" with ''[[directed cycle]]''.

The definition and properties of Eulerian trails, cycles and graphs are valid for [[multigraph]]s as well.

An '''Eulerian orientation''' of an undirected graph ''G'' is an assignment of a direction to each edge of ''G'' such that, at each vertex ''v'', the [[Directed graph#Indegree and outdegree|indegree]] of ''v'' equals the [[Directed graph#Indegree and outdegree|outdegree]] of ''v''. Such an orientation exists for any undirected graph in which every vertex has even degree, and may be found by constructing an Euler tour in each connected component of ''G'' and then orienting the edges according to the tour.<ref>{{citation
 | last = Schrijver | first = A. | author-link = Alexander Schrijver
 | doi = 10.1007/BF02579193
 | issue = 3–4
 | journal = Combinatorica
 | mr = 729790
 | pages = 375–380
 | title = Bounds on the number of Eulerian orientations
 | volume = 3
 | year = 1983| s2cid = 13708977 | url = https://ir.cwi.nl/pub/10053 }}.</ref> Every Eulerian orientation of a connected graph is a [[strong orientation]], an orientation that makes the resulting directed graph [[strongly connected]].

== Properties ==
*An undirected graph has an Eulerian cycle if and only if every vertex has even degree, and all of its vertices with nonzero degree belong to a single [[Connected component (graph theory)|connected component]].<ref name=ptw>{{citation
 | last1 = Pólya | first1 = George | author1-link = George Pólya
 | last2 = Tarjan | first2 = Robert E. | author2-link = Robert Tarjan
 | last3 = Woods | first3 = Donald R. | author3-link = Don Woods (programmer)
 | contribution = Hamiltonian and Eulerian Paths
 | date = October 2009
 | doi = 10.1007/978-0-8176-4953-1_13
 | isbn = 9780817649531
 | pages = 157–168
 | publisher = Birkhäuser Boston
 | title = Notes on Introductory Combinatorics}}</ref>
*An undirected graph can be decomposed into edge-disjoint [[cycle (graph theory)|cycle]]s if and only if all of its vertices have even degree. So, a graph has an Eulerian cycle if and only if it can be decomposed into edge-disjoint cycles and its nonzero-degree vertices belong to a single connected component.
*An undirected graph has an Eulerian trail if and only if exactly zero or two vertices have odd degree, and all of its vertices with nonzero degree belong to a single connected component.<ref name=ptw/>
*A directed graph has an Eulerian cycle if and only if every vertex has equal [[in degree (graph theory)|in degree]] and [[out degree (graph theory)|out degree]], and all of its vertices with nonzero degree belong to a single [[strongly connected component]]. Equivalently, a directed graph has an Eulerian cycle if and only if it can be decomposed into edge-disjoint [[cycle (graph theory)|directed cycle]]s and all of its vertices with nonzero degree belong to a single strongly connected component.<ref name=ptw/>
*A directed graph has an Eulerian trail if and only if at most one vertex has {{nowrap|1=([[out degree (graph theory)|out-degree]]) &minus; ([[in degree (graph theory)|in-degree]]) = 1,}} at most one vertex has {{nowrap|1=(in-degree) &minus; (out-degree) = 1,}} every other vertex has equal in-degree and out-degree, and all of its vertices with nonzero degree belong to a single connected component of the underlying undirected graph.<ref name=ptw/>

== Constructing Eulerian trails and circuits ==
[[File:Eulerian_path_puzzles.svg|thumb|Using Eulerian trails to solve puzzles involving drawing a shape with a continuous stroke: {{olist
    |As the [[:de:Haus vom Nikolaus|Haus vom Nikolaus puzzle]] has two odd-degree vertices (orange), the trail must start at one and end at the other.
    |A variant with four odd-degree vertices has no solution.
    |If there are no odd-degree vertices, the trail can start anywhere and forms an Eulerian cycle.
    |Loose ends are considered vertices of degree 1.
    |The graph must also be connected.
}}]]

=== Fleury's algorithm ===
'''Fleury's algorithm''' is an elegant but inefficient algorithm that dates to 1883.<ref>{{citation|first=Pierre-Henry<!-- See https://hsm.stackexchange.com/questions/12633/who-was-fleury-and-what-was-his-first-name -- in the publication, the "M." in "M. Fleury" is just short for monsieur, and should not be listed as Fleury's first initial -->|last=Fleury|title=Deux problèmes de Géométrie de situation|language=fr|url=https://books.google.com/books?id=l-03AAAAMAAJ&pg=PA257|journal=Journal de mathématiques élémentaires|series=2nd ser.|volume=2|year=1883|pages=257–261}}.</ref> Consider a graph known to have all edges in the same component and at most two vertices of odd degree. The algorithm starts at a vertex of odd degree, or, if the graph has none, it starts with an arbitrarily chosen vertex. At each step it chooses the next edge in the path to be one whose deletion would not disconnect the graph, unless there is no such edge, in which case it picks the remaining edge left at the current vertex. It then moves to the other endpoint of that edge and deletes the edge. At the end of the algorithm there are no edges left, and the sequence from which the edges were chosen forms an Eulerian cycle if the graph has no vertices of odd degree, or an Eulerian trail if there are exactly two vertices of odd degree.

While the ''graph traversal'' in Fleury's algorithm is linear in the number of edges, i.e. <math>O(|E|)</math>, we also need to factor in the complexity of detecting [[Bridge (graph theory)|bridge]]s. If we are to re-run [[Robert Tarjan|Tarjan]]'s linear time [[Bridge (graph theory)#Tarjan's bridge-finding algorithm|bridge-finding algorithm]]<ref>{{citation
 | last = Tarjan | first = R. Endre | author-link = Robert Tarjan
 | doi = 10.1016/0020-0190(74)90003-9
 | year = 1974
 | issue = 6
 | journal = Information Processing Letters
 | mr = 0349483
 | pages = 160–161
 | title = A note on finding the bridges of a graph
 | volume = 2}}.</ref> after the removal of every edge,  Fleury's algorithm will have a time complexity of <math>O(|E|^2)</math>. A dynamic bridge-finding algorithm of {{harvtxt|Thorup|2000}} allows this to be improved to <math>O(|E| \cdot \log^3 |E| \cdot \log \log |E|)</math>, but this is still significantly slower than alternative algorithms.

=== Hierholzer's algorithm ===
[[Carl Hierholzer|Hierholzer]]'s 1873 paper provides a different method for finding Euler cycles that is more efficient than Fleury's algorithm:
*Choose any starting vertex ''v'', and follow a trail of edges from that vertex until returning to ''v''. It is not possible to get stuck at any vertex other than ''v'', because the even degree of all vertices ensures that, when the trail enters another vertex ''w'' there must be an unused edge leaving ''w''. The tour formed in this way is a closed tour, but may not cover all the vertices and edges of the initial graph.
*As long as there exists a vertex ''u'' that belongs to the current tour but that has adjacent edges not part of the tour, start another trail from ''u'', following unused edges until returning to ''u'', and join the tour formed in this way to the previous tour.
*Since we assume the original graph is [[connected graph|connected]], repeating the previous step will exhaust all edges of the graph.
By using a data structure such as a [[doubly linked list]] to maintain the set of unused edges incident to each vertex, to maintain the list of vertices on the current tour that have unused edges, and to maintain the tour itself, the individual operations of the algorithm (finding unused edges exiting each vertex, finding a new starting vertex for a tour, and connecting two tours that share a vertex) may be performed in constant time each, so the overall algorithm takes [[linear time]], <math>O(|E|)</math>.<ref>{{citation|title=Eulerian Graphs and Related Topics: Part 1, Volume 2|volume=50|series=Annals of Discrete Mathematics|first=Herbert|last=Fleischner|publisher=Elsevier|year=1991|isbn=978-0-444-89110-5|contribution=X.1 Algorithms for Eulerian Trails|pages=[https://archive.org/details/euleriangraphsre0001flei/page/ X.1–13]|url=https://archive.org/details/euleriangraphsre0001flei/page/}}.</ref>

This algorithm may also be implemented with a [[Double-ended queue|deque]]. Because it is only possible to get stuck when the deque represents a closed tour, one should rotate the deque by removing edges from the tail and adding them to the head until unstuck, and then continue until all edges are accounted for. This also takes linear time, as the number of rotations performed is never larger than <math>|E|</math> (intuitively, any "bad" edges are moved to the head, while fresh edges are added to the tail)
{{Hamiltonian_platonic_graphs.svg}}

==Counting Eulerian circuits==

=== Complexity issues ===
The number of Eulerian circuits in ''[[Directed graph|digraphs]]'' can be calculated using the so-called '''[[BEST theorem]]''', named after [[N. G. de Bruijn|de '''B'''ruijn]], [[Tatyana Pavlovna Ehrenfest|van Aardenne-'''E'''hrenfest]], [[Cedric Smith (statistician)|'''S'''mith]] and [[W. T. Tutte|'''T'''utte]].  The formula states that the number of Eulerian circuits in a digraph is the product of certain degree factorials and the number of rooted [[Arborescence (graph theory)|arborescences]].  The latter can be computed as a [[determinant]], by the [[matrix tree theorem]], giving a polynomial time algorithm.

BEST theorem is first stated in this form in a "note added in proof" to the Aardenne-Ehrenfest and de Bruijn paper (1951).  The original proof was [[bijective proof|bijective]] and generalized the [[de Bruijn sequence]]s.  It is a variation on an earlier result by Smith and Tutte (1941).

Counting the number of Eulerian circuits on ''undirected'' graphs is much more difficult. This problem is known to be [[Sharp-P-complete|#P-complete]].<ref>Brightwell and [[Peter Winkler|Winkler]], "[http://www.cdam.lse.ac.uk/Reports/Files/cdam-2004-12.pdf Note on Counting Eulerian Circuits]", 2004.</ref> In a positive direction, a [[Markov chain Monte Carlo]] approach, via the ''Kotzig transformations'' (introduced by [[Anton Kotzig]] in 1968) is believed to give a sharp approximation for the number of Eulerian circuits in a graph, though as yet there is no proof of this fact (even for graphs of bounded degree).

=== Special cases ===
An [[Asymptotic analysis|asymptotic formula]] for the number of Eulerian circuits in the [[complete graph]]s was determined by [[Brendan McKay (mathematician)|McKay]] and Robinson (1995):<ref>[[Brendan McKay (mathematician)|Brendan McKay]] and Robert W. Robinson, [http://cs.anu.edu.au/~bdm/papers/euler.pdf Asymptotic enumeration of eulerian circuits in the complete graph], ''[[Combinatorica]]'', 10 (1995), no. 4, 367–377.</ref>
:<math>
\operatorname{ec}(K_n) = 2^{\frac{(n+1)}{2}}\pi^{\frac{1}{2}} e^{\frac{-n^2}{2}+\frac{11}{12}} n^{\frac{(n-2)(n+1)}{2}} \bigl(1+O(n^{-\frac{1}{2}+\epsilon})\bigr).
</math>

A similar formula was later obtained by M.I. Isaev (2009) for [[complete bipartite graph]]s:<ref>{{cite journal |author=M.I. Isaev |title=Asymptotic number of Eulerian circuits in complete bipartite graphs |language=ru |journal=Proc. 52-nd MFTI Conference |year=2009 |place=Moscow |pages=111–114 }}</ref>
:<math>
\operatorname{ec}(K_{n,n}) = \left(\frac{n}{2}-1\right)!^{2n} 2^{n^2-n+\frac{1}{2}}\pi^{-n+\frac{1}{2}} n^{n-1}  \bigl(1+O(n^{-\frac{1}{2}+\epsilon})\bigr).
</math>

== Applications ==
Eulerian trails are used in [[bioinformatics]] to reconstruct the [[DNA sequence]] from its fragments.<ref>{{cite journal| last1=Pevzner| first1=Pavel A.| last2=Tang| first2=Haixu| last3=Waterman| first3=Michael S.| year=2001 |title=An Eulerian trail approach to DNA fragment assembly |journal=Proceedings of the National Academy of Sciences of the United States of America |volume=98| pmid=11504945 |issue=17 |pages=9748–9753| pmc=55524 |doi=10.1073/pnas.171285098 | bibcode=2001PNAS...98.9748P| doi-access=free}}</ref> They are also used in [[CMOS]] circuit design to find an optimal [[logic gate]] ordering.<ref>{{cite journal| last1=Roy| first1=Kuntal| year=2007 |title=Optimum Gate Ordering of CMOS Logic Gates Using Euler Path Approach: Some Insights and Explanations |journal=Journal of Computing and Information Technology |volume=15 |issue=1 |pages=85–92|doi=10.2498/cit.1000731 |doi-access=free }}</ref> There are some algorithms for processing [[Tree (graph theory)|tree]]s that rely on an Euler tour of the tree (where each edge is treated as a pair of arcs).<ref>{{cite journal|last1=Tarjan|first1=Robert E.|last2=Vishkin|first2=Uzi|title=An efficient parallel biconnectivity algorithm|journal=SIAM Journal on Computing|date=1985|volume=14|number=4|pages=862–874|doi=10.1137/0214061|citeseerx=10.1.1.465.8898}}</ref><ref>{{cite journal|last1=Berkman|first1=Omer|last2=Vishkin|first2=Uzi|title=Finding level-ancestors in trees|journal=J. Comput. Syst. Sci.|date=Apr 1994|volume=48|issue=2|series=2|pages=214–230|doi=10.1016/S0022-0000(05)80002-9|doi-access=}}</ref> The [[de Bruijn sequence]]s can be constructed as Eulerian trails of [[de Bruijn graph]]s.<ref>{{Cite journal|last=Savage|first=Carla|date=January 1997|title=A Survey of Combinatorial Gray Codes|journal=SIAM Review|volume=39|issue=4|pages=605–629|doi=10.1137/S0036144595295272|issn=0036-1445}}</ref>

==In infinite graphs==
[[File:Kely graph of F2 clear.svg|thumb|An infinite graph with all vertex degrees equal to four but with no Eulerian line]]
In an [[infinite graph]], the corresponding concept to an Eulerian trail or Eulerian cycle is an Eulerian line, a doubly-infinite trail that covers all of the edges of the graph. It is not sufficient for the existence of such a trail that the graph be connected and that all vertex degrees be even; for instance, the infinite [[Cayley graph]] shown, with all vertex degrees equal to four, has no Eulerian line. The infinite graphs that contain Eulerian lines were characterized by {{harvtxt|Erdős|Grünwald|Weiszfeld|1936}}. For an infinite graph or multigraph {{mvar|G}} to have an Eulerian line, it is necessary and sufficient that all of the following conditions be met:<ref>{{citation
 | last = Komjáth | first = Peter | author-link = Péter Komjáth
 | contribution = Erdős's work on infinite graphs
 | contribution-url = https://books.google.com/books?id=7_zFBAAAQBAJ&pg=PA325
 | doi = 10.1007/978-3-642-39286-3_11
 | mr = 3203602
 | pages = 325–345
 | publisher = János Bolyai Math. Soc., Budapest
 | series = Bolyai Soc. Math. Stud.
 | title = Erdös centennial
 | volume = 25
 | year = 2013}}.</ref><ref>{{citation
 | last = Bollobás | first = Béla | author-link = Béla Bollobás
 | doi = 10.1007/978-1-4612-0619-4
 | isbn = 0-387-98488-7
 | mr = 1633290
 | page = 20
 | publisher = Springer-Verlag, New York
 | series = Graduate Texts in Mathematics
 | title = Modern graph theory
 | url = https://books.google.com/books?id=JeIlBQAAQBAJ&pg=PA20
 | volume = 184
 | year = 1998}}.</ref>
*{{mvar|G}} is connected.
*{{mvar|G}} has [[countable set]]s of vertices and edges.
*{{mvar|G}} has no vertices of (finite) odd degree.
*Removing any finite subgraph {{mvar|S}} from {{mvar|G}} leaves at most two infinite connected components in the remaining graph, and if {{mvar|S}} has even degree at each of its vertices then removing {{mvar|S}} leaves exactly one infinite connected component.

== Undirected Eulerian graphs ==
Euler stated a necessary condition for a finite graph to be Eulerian as all vertices must have even degree. Hierholzer proved this is a sufficient condition in a paper published in 1873. This leads to the following necessary and sufficient statement for what a finite graph must have to be Eulerian: An undirected connected finite graph is Eulerian if and only if every vertex of G has even degree.<ref name=":0">{{Cite book |title=Arc Routing: Problems, Methods, and Applications |url=https://epubs.siam.org/doi/book/10.1137/1.9781611973679 |access-date=2022-08-19 |series=MOS-SIAM Series on Optimization |publisher=SIAM|year=2015 |language=en |doi=10.1137/1.9781611973679|isbn=978-1-61197-366-2 |editor-last1=Corberán |editor-last2=Laporte |editor-first1=Ángel |editor-first2=Gilbert }}</ref>

The following result was proved by Veblen in 1912: An undirected connected graph is Eulerian if and only if it is the disjoint union of some cycles.<ref name=":0" />[[File:Even directed graph that is not Eulerian counterexample.svg|alt=A directed graph with all even degrees that is not Eulerian, serving as a counterexample to the statement that a sufficient condition for a directed graph to be Eulerian is that it has all even degrees|thumb|A directed graph with all even degrees that is not Eulerian, serving as a counterexample to the statement that a sufficient condition for a directed graph to be Eulerian is that it has all even degrees]]Hierholzer developed a linear time algorithm for constructing an Eulerian tour in an undirected graph.

== Directed Eulerian graphs ==
It is possible to have a [[directed graph]] that has all even out-degrees but is not Eulerian. Since an Eulerian circuit leaves a vertex the same number of times as it enters that vertex, a necessary condition for an Eulerian circuit to exist is that the in-degree and out-degree are equal at each vertex. Obviously, connectivity is also necessary. König proved that these conditions are also sufficient. That is, a directed graph is Eulerian if and only if it is connected and the in-degree and out-degree are equal at each vertex.<ref name=":0" />

In this theorem it doesn't matter whether "connected" means "weakly connected" or "strongly connected" since they are equivalent for Eulerian graphs.

Hierholzer's linear time algorithm for constructing an Eulerian tour is also applicable to directed graphs.<ref name=":0" />

== Mixed Eulerian graphs ==
[[File:Eulerian mixed graph that is even but not symmetric proving that evenness and symmetricness is not a necessary and sufficient condition for a mixed graph to be Eulerian.svg|alt=This mixed graph is Eulerian. The graph is even but not symmetric which proves that evenness and symmetricness are not necessary and sufficient conditions for a mixed graph to be Eulerian.|thumb|This mixed graph is Eulerian. The graph is even but not symmetric which proves that evenness and symmetricness are not necessary and sufficient conditions for a mixed graph to be Eulerian.]]
All [[Mixed graph|mixed graphs]] that are both even and symmetric are guaranteed to be Eulerian. However, this is not a necessary condition, as it is possible to construct a non-symmetric, even graph that is Eulerian.<ref name=":0"/>

[[L._R._Ford_Jr.|Ford]] and [[D._R._Fulkerson|Fulkerson]] proved in 1962 in their book ''Flows in Networks''<ref>{{cite book
 | author = L. R. Ford 
 |author2=D. R. Fulkerson
 | year = 1962
 | title = Flows in Networks
 | url = https://archive.org/details/flowsinnetworks0000ford
 | url-access = registration
 | publisher = Princeton University Press
 | location = Princeton, NJ
|isbn=9780691079622
 }}</ref> 
a necessary and sufficient condition for a graph to be Eulerian, viz., that every vertex must be even and satisfy the balance condition, i.e. for every subset of vertices S, the difference between the number of arcs leaving S and entering S must be less than or equal to the number of edges incident with S.<ref name=":0" />

The process of checking if a mixed graph is Eulerian is harder than checking if an undirected or directed graph is Eulerian because the balanced set condition concerns every possible subset of vertices.

== Eulerian cycles and bridges ==
Define an '''Eulerian graph''' as a graph with an Eulerian cycle. Every Eulerian graph is a [[bridgeless graph]]. This is because in an Eulerian graph every edge is a part of an Eulerian cycle. Hence, if the edge is deleted, then its endpoints remain connected through the rest of the cycle. But the opposite is not true.

Define an '''almost Eulerian graph''' as a graph that can be made Eulerian by adding a single edge (equivalently, a graph that contains an Eulerian trail). Every almost-Eulerian graph is almost-bridgeless, but the opposite is not true.

The classes of bridgeless graphs and almost-Eulerian graphs have a non-empty intersection (the Eulerian graphs are both bridgeless and almost-Eulerian), but they do not contain each other.<ref>{{Cite journal |last=Bei |first=Xiaohui |last2=Elkind |first2=Edith |last3=Segal-Halevi |first3=Erel |last4=Suksompong |first4=Warut |date=2025-03-31 |title=Dividing a Graphical Cake |url=https://epubs.siam.org/doi/full/10.1137/22M1500502 |journal=SIAM Journal on Discrete Mathematics |volume=39 |issue=1 |pages=19–54 |doi=10.1137/22M1500502 |issn=0895-4801}}</ref>{{Rp|location=Appendix.B}}[[File:Even mixed graph that violates the balanced set condition and is therefore not Eulerian.svg|alt=An even mixed graph that violates the balanced set condition and is therefore not Eulerian.|thumb|An even mixed graph that violates the balanced set condition and is therefore not Eulerian.]]
[[File:Even mixed graph satisfies the balanced set condition and is therefore an Eulerian mixed graph.svg|alt=An even mixed graph that satisfies the balanced set condition and is therefore an Eulerian mixed graph.|thumb|An even mixed graph that satisfies the balanced set condition and is therefore an Eulerian mixed graph.]]

== See also ==
* [[Eulerian matroid]], an abstract generalization of Eulerian graphs
* [[Five room puzzle]]
* [[Handshaking lemma]], proven by Euler in his original paper, showing that any undirected connected graph has an even number of odd-degree vertices
* [[Hamiltonian path]] – a path that visits each ''vertex'' exactly once.
* [[Route inspection problem]], search for the shortest path that visits all edges, possibly repeating edges if an Eulerian path does not exist. 
* [[Veblen's theorem]], which states that graphs with even vertex degree can be partitioned into edge-disjoint cycles regardless of their connectivity

== Notes ==
<references group="note" />

== References ==
{{reflist|2}}

== Bibliography ==
*{{citation
 | last1 = Erdős | first1 = Pál | author1-link = Paul Erdős
 | last2 = Grünwald | first2 = Tibor | author2-link = Tibor Gallai
 | last3 = Weiszfeld | first3 = Endre | author3-link = Andrew Vázsonyi
 | journal = Mat. Fix. Lapok
 | pages = 129–140
 | title = Végtelen gráfok Euler vonalairól
 | trans-title = On Euler lines of infinite graphs
 | language = hu
 | url = https://www.renyi.hu/~p_erdos/1936-11.pdf
 | volume = 43
 | year = 1936}}.  Translated as {{citation
 | last1 = Erdős | first1 = P. | author1-link = Paul Erdős
 | last2 = Grünwald | first2 = T. | author2-link = Tibor Gallai
 | last3 = Vázsonyi | first3 = E.
 | journal = J. Math. Phys.
 | language = de
 | pages = 59–75
 | title = Über Euler-Linien unendlicher Graphen
 |trans-title=On Eulerian lines in infinite graphs
 | url = http://www.renyi.hu/~p_erdos/1938-15.pdf
 | volume = 17
 | issue = 1–4 | year = 1938
 | doi = 10.1002/sapm193817159}}.
* Euler, L., "[http://www.math.dartmouth.edu/~euler/pages/E053.html Solutio problematis ad geometriam situs pertinentis]", ''Comment. Academiae Sci. I. Petropolitanae'' '''8''' (1736), 128–140.
*{{citation
 | last = Hierholzer | first = Carl | author-link = Carl Hierholzer
 | doi = 10.1007/BF01442866
 | issue = 1
 | journal = [[Mathematische Annalen]]
 | pages = 30–32
 | title = Ueber die Möglichkeit, einen Linienzug ohne Wiederholung und ohne Unterbrechung zu umfahren
 | volume = 6
 | year = 1873| s2cid = 119885172 | url = https://zenodo.org/record/1447429
 }}.
* Lucas, E., ''Récréations Mathématiques IV'', Paris, 1921.
* Fleury, "Deux problemes de geometrie de situation", ''Journal de mathematiques elementaires'' (1883), 257–261.
* [[Tatyana Pavlovna Ehrenfest|T. van Aardenne-Ehrenfest]] and [[Nicolaas Govert de Bruijn|N. G. de Bruijn]] (1951) "Circuits and trees in oriented linear graphs", [[Simon Stevin (journal)|Simon Stevin]] 28: 203–217.
*{{Citation|first=Mikkel|last=Thorup|author-link=Mikkel Thorup|year=2000|pages=343–350|doi=10.1145/335305.335345|contribution=Near-optimal {{Sic|hide=y|fully|-}}dynamic graph connectivity|title=Proc. 32nd ACM Symposium on Theory of Computing|title-link=Symposium on Theory of Computing|s2cid=128282}}
* [[W. T. Tutte]] and [[Cedric Smith (statistician)|C. A. B. Smith]] (1941) "On Unicursal Paths in a Network of Degree 4", [[American Mathematical Monthly]] 48: 233–237.

== External links ==
{{Commons category|Eulerian paths}}
* [http://mathforum.org/kb/message.jspa?messageID=3648262&tstart=135 Discussion of early mentions of Fleury's algorithm].
* [http://www.encyclopediaofmath.org/index.php/Euler_tour ''Euler tour''] at [[Encyclopedia of Mathematics]].

[[Category:Graph theory objects]]
[[Category:Leonhard Euler]]