1556:
1586:
1578:
1521:
31:
414:
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.
768:
1439:
375:
50:
1159:
1392:
734:. 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
1450:, 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
1513:
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:
683:
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,
413:
is an elegant but inefficient algorithm that dates to 1883. 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
1570:
Ford and
Fulkerson proved in 1962 in their book Flows in Networks 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
1540:
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
1555:
934:
166:
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
1174:
323:
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
1574:
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.
616:
1524:
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
1154:{\displaystyle \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 )}.}
155:
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.
1541:
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.
1387:{\displaystyle \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 )}.}
1559:
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.
798:
1567:
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.
327:
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
1585:
908:
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).
1577:
365:
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.
291:. 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
516:
230:
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.
725:
458:
762:
791:
53:
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.
1544:
In this theorem it doesn't matter whether "connected" means "weakly connected" or "strongly connected" since they are equivalent for Eulerian graphs.
312:
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
1517:
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.
784:
877:
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
132:
with all vertices of even degree have an Eulerian circuit. The first complete proof of this latter claim was published posthumously in 1873 by
2345:
1970:
862:. The formula states that the number of Eulerian circuits in a digraph is the product of certain degree factorials and the number of rooted
1454:
shown, with all vertex degrees equal to four, has no Eulerian line. The infinite graphs that contain Eulerian lines were characterized by
1733:
226:. The term "Eulerian graph" is also sometimes used in a weaker sense to denote a graph where every vertex has even degree. For finite
313:
2291:
1878:
1711:
1520:
30:
2521:
525:
1635:, which states that graphs with even vertex degree can be partitioned into edge-disjoint cycles regardless of their connectivity
1613:, proven by Euler in his original paper, showing that any undirected connected graph has an even number of odd-degree vertices
98:
38:
2594:
2553:
2002:
925:
1682:. This ambiguity can be avoided by using the terms Eulerian trail and Eulerian circuit when self-intersection is allowed.
339:
239:
74:
1702:
2578:
2549:
863:
849:
129:
684:
and connecting two tours that share a vertex) may be performed in constant time each, so the overall algorithm takes
2502:
841:
629:'s 1873 paper provides a different method for finding Euler cycles that is more efficient than Fleury's algorithm:
1629:, search for the shortest path that visits all edges, possibly repeating edges if an Eulerian path does not exist.
653:. The tour formed in this way is a closed tour, but may not cover all the vertices and edges of the initial graph.
2506:
352:
335:
1626:
1165:
897:
356:
331:
1781:
342:. Equivalently, a directed graph has an Eulerian cycle if and only if it can be decomposed into edge-disjoint
2599:
1547:
Hierholzer's linear time algorithm for constructing an Eulerian tour is also applicable to directed graphs.
660:
that belongs to the current tour but that has adjacent edges not part of the tour, start another trail from
121:
that a necessary condition for the existence of Eulerian circuits is that all vertices in the graph have an
45:
have more than two odd vertices (in orange), thus are not Eulerian and hence the puzzles have no solutions.
2510:
2141:
1858:
295:
and then orienting the edges according to the tour. Every Eulerian orientation of a connected graph is a
2566:
2460:
1768:
469:
461:
125:
90:
1589:
An even mixed graph that satisfies the balanced set condition and is therefore an Eulerian mixed graph.
1528:
Hierholzer developed a linear time algorithm for constructing an Eulerian tour in an undirected graph.
1462:
to have an Eulerian line, it is necessary and sufficient that all of the following conditions be met:
2101:"Optimum Gate Ordering of CMOS Logic Gates Using Euler Path Approach: Some Insights and Explanations"
2053:
343:
320:
215:
159:
122:
110:
70:
2146:
1793:
1632:
1514:
An undirected connected finite graph is Eulerian if and only if every vertex of G has even degree.
1419:
917:
871:
106:
78:
2269:
2231:
2535:
2477:
1825:
1750:
1423:
882:
772:
731:
680:
300:
296:
118:
2378:
475:
2341:
2287:
2242:, Bolyai Soc. Math. Stud., vol. 25, János Bolyai Math. Soc., Budapest, pp. 325–345,
2235:
2213:
2081:
1966:
1894:
1874:
1707:
1610:
767:
764:(intuitively, any "bad" edges are moved to the head, while fresh edges are added to the tail)
2456:"Ueber die Möglichkeit, einen Linienzug ohne Wiederholung und ohne Unterbrechung zu umfahren"
2273:
1962:
1956:
645:, because the even degree of all vertices ensures that, when the trail enters another vertex
2527:
2469:
2425:
2333:
2279:
2243:
2205:
2178:
2151:
2112:
2071:
2061:
1929:
1866:
1809:
1742:
1616:
1605:
1599:
893:
691:
424:
346:
and all of its vertices with nonzero degree belong to a single strongly connected component.
188:
42:
2301:
2255:
1990:
1941:
1821:
1581:
An even mixed graph that violates the balanced set condition and is therefore not Eulerian.
1422:
that rely on an Euler tour of the tree (where each edge is treated as a pair of arcs). The
383:
378:
Using Eulerian trails to solve puzzles involving drawing a shape with a continuous stroke:
2451:
2327:
2297:
2251:
2132:
Tarjan, Robert E.; Vishkin, Uzi (1985). "An efficient parallel biconnectivity algorithm".
2025:
M.I. Isaev (2009). "Asymptotic number of Eulerian circuits in complete bipartite graphs".
1937:
1817:
1427:
878:
833:
672:
626:
227:
133:
113:; i.e., a path starting and ending on the same vertex) that visits each edge exactly once?
2572:
1850:
737:
2057:
2437:
2278:, Graduate Texts in Mathematics, vol. 184, Springer-Verlag, New York, p. 20,
1537:
1447:
1438:
1403:
921:
822:
392:
If there are no odd vertices, the trail can start anywhere and forms an Eulerian cycle.
284:
276:
245:
234:
191:
is a walk that uses each edge exactly once. If such a walk exists, the graph is called
158:
For the existence of Eulerian trails it is necessary that zero or two vertices have an
144:
94:
2182:
374:
2588:
2517:
2481:
2401:
2370:
2076:
2041:
2011:
1986:
1933:
1917:
1854:
1476:
465:
1829:
472:
after the removal of every edge, Fleury's algorithm will have a time complexity of
2405:
2374:
1451:
1407:
905:
828:
58:
49:
2539:
252:
The definition and properties of Eulerian trails, cycles and graphs are valid for
2247:
1870:
1442:
An infinite graph with all vertex degrees equal to four but with no Eulerian line
2545:
1564:
1496:
leaves at most two infinite connected components in the remaining graph, and if
867:
856:
685:
386:
has two odd vertices (orange), the trail must start at one and end at the other.
2046:
Proceedings of the National Academy of Sciences of the United States of America
775:
of the vertices of the five platonic solids – only the octahedron has an
218:
that uses each edge exactly once. If such a cycle exists, the graph is called
2283:
2209:
1780:
Schaum's outline of theory and problems of graph theory By V. K. Balakrishnan
1725:
1571:
entering S must be less than or equal to the number of edges incident with S.
1415:
253:
34:
2217:
2006:
349:
A directed graph has an Eulerian trail if and only if at most one vertex has
330:
A directed graph has an Eulerian cycle if and only if every vertex has equal
2382:
2337:
2169:
Berkman, Omer; Vishkin, Uzi (Apr 1994). "Finding level-ancestors in trees".
2409:
2085:
2066:
2531:
2429:
17:
2117:
2100:
2473:
1813:
1754:
2196:
Savage, Carla (January 1997). "A Survey of Combinatorial Gray Codes".
1666:
path and cycle. A (potentially) self-intersecting path is known as a
618:, but this is still significantly slower than alternative algorithms.
885:. It is a variation on an earlier result by Smith and Tutte (1941).
101:
problem in 1736. The problem can be stated mathematically like this:
2455:
2155:
1746:
1726:"Two-graphs, switching classes and Euler graphs are equal in number"
1961:, Annals of Discrete Mathematics, vol. 50, Elsevier, pp.
1955:
Fleischner, Herbert (1991), "X.1 Algorithms for Eulerian Trails",
1584:
1576:
1554:
1519:
1437:
766:
675:, repeating the previous step will exhaust all edges of the graph.
637:, and follow a trail of edges from that vertex until returning to
48:
29:
2007:
Asymptotic enumeration of eulerian circuits in the complete graph
338:, and all of its vertices with nonzero degree belong to a single
1411:
81:
exactly once (allowing for revisiting vertices). Similarly, an
1797:
1164:
A similar formula was later obtained by M.I. Isaev (2009) for
2040:
Pevzner, Pavel A.; Tang, Haixu; Waterman, Michael S. (2001).
421:
in Fleury's algorithm is linear in the number of edges, i.e.
668:, and join the tour formed in this way to the previous tour.
105:
Given the graph in the image, is it possible to construct a
892:
graphs is much more difficult. This problem is known to be
641:. It is not possible to get stuck at any vertex other than
611:{\displaystyle O(|E|\cdot \log ^{3}|E|\cdot \log \log |E|)}
2520:(2000), "Near-optimal fully-dynamic graph connectivity",
319:
An undirected graph can be decomposed into edge-disjoint
299:, an orientation that makes the resulting directed graph
460:, we also need to factor in the complexity of detecting
2509:(1951) "Circuits and trees in oriented linear graphs",
2552:(1941) "On Unicursal Paths in a Network of Degree 4",
1500:
has even degree at each of its vertices then removing
1455:
89:
is an Eulerian trail that starts and ends on the same
2042:"An Eulerian trail approach to DNA fragment assembly"
1177:
937:
740:
694:
528:
478:
427:
2495:
Fleury, "Deux problemes de geometrie de situation",
1958:
Eulerian Graphs and Related Topics: Part 1, Volume 2
1920:(1974), "A note on finding the bridges of a graph",
779:
or cycle, by extending its path with the dotted one
771:
Orthographic projections and Schlegel diagrams with
389:
Annie Pope's with four odd vertices has no solution.
2438:
Solutio problematis ad geometriam situs pertinentis
1418:ordering. There are some algorithms for processing
2567:Discussion of early mentions of Fleury's algorithm
1861:(October 2009), "Hamiltonian and Eulerian Paths",
1386:
1153:
756:
719:
610:
510:
452:
1674:; and a (potentially) self-intersecting cycle, a
2329:Arc Routing: Problems, Methods, and Applications
2326:Corberán, Ángel; Laporte, Gilbert, eds. (2015).
1504:leaves exactly one infinite connected component.
267:is an assignment of a direction to each edge of
2523:Proc. 32nd ACM Symposium on Theory of Computing
2412:[On Eulerian lines in infinite graphs]
2105:Journal of Computing and Information Technology
1798:"Bounds on the number of Eulerian orientations"
1602:, an abstract generalization of Eulerian graphs
395:Loose ends are considered vertices of degree 1.
730:This algorithm may also be implemented with a
1376:
1328:
1143:
1095:
792:
8:
2385:[On Euler lines of infinite graphs]
888:Counting the number of Eulerian circuits on
664:, following unused edges until returning to
1700:N. L. Biggs, E. K. Lloyd and R. J. Wilson,
1650:
1648:
920:for the number of Eulerian circuits in the
162:degree; this means the Königsberg graph is
27:Trail in a graph that visits each edge once
1895:"Deux problèmes de Géométrie de situation"
1410:from its fragments. They are also used in
799:
785:
2442:Comment. Academiae Sci. I. Petropolitanae
2332:. MOS-SIAM Series on Optimization. SIAM.
2145:
2116:
2075:
2065:
1426:can be constructed as Eulerian trails of
1375:
1374:
1353:
1349:
1327:
1326:
1314:
1298:
1288:
1272:
1257:
1252:
1239:
1214:
1191:
1176:
1142:
1141:
1120:
1116:
1094:
1093:
1053:
1037:
1022:
1012:
1011:
996:
967:
951:
936:
749:
741:
739:
709:
701:
693:
600:
592:
572:
564:
555:
543:
535:
527:
499:
494:
485:
477:
442:
434:
426:
370:Constructing Eulerian trails and circuits
518:. A dynamic bridge-finding algorithm of
373:
2410:"Über Euler-Linien unendlicher Graphen"
1865:, Birkhäuser Boston, pp. 157–168,
1724:C. L. Mallows, N. J. A. Sloane (1975).
1693:
1644:
1485:has no vertices of (finite) odd degree.
1706:, Clarendon Press, Oxford, 1976, 8–9,
1458:. For an infinite graph or multigraph
1456:Erdõs, Grünwald & Weiszfeld (1936)
874:, giving a polynomial time algorithm.
826:can be calculated using the so-called
671:Since we assume the original graph is
519:
2497:Journal de mathematiques elementaires
2321:
2319:
2317:
2315:
2313:
2311:
1899:Journal de mathématiques élémentaires
1845:
1843:
1841:
1839:
649:there must be an unused edge leaving
363:(in-degree) − (out-degree) = 1,
143:A connected graph has an Euler cycle
7:
679:By using a data structure such as a
1863:Notes on Introductory Combinatorics
1734:SIAM Journal on Applied Mathematics
866:. The latter can be computed as a
820:The number of Eulerian circuits in
2383:"Végtelen gráfok Euler vonalairól"
1991:Note on Counting Eulerian Circuits
1414:circuit design to find an optimal
25:
2236:"Erdős's work on infinite graphs"
656:As long as there exists a vertex
398:The graph must also be connected.
237:, "path" has to be replaced with
128:, and stated without proof that
93:. They were first discussed by
2029:(in Russian). Moscow: 111–114.
1922:Information Processing Letters
1654:Some people reserve the terms
1371:
1342:
1203:
1184:
1138:
1109:
1083:
1071:
1068:
1056:
982:
970:
957:
944:
750:
742:
714:
710:
702:
698:
605:
601:
593:
573:
565:
544:
536:
532:
522:allows this to be improved to
505:
495:
486:
482:
447:
443:
435:
431:
214:, in an undirected graph is a
1:
2554:American Mathematical Monthly
2183:10.1016/S0022-0000(05)80002-9
1893:Fleury, Pierre-Henry (1883),
1488:Removing any finite subgraph
896:. In a positive direction, a
147:every vertex has even degree.
2490:Récréations Mathématiques IV
2248:10.1007/978-3-642-39286-3_11
2015:, 10 (1995), no. 4, 367–377.
1934:10.1016/0020-0190(74)90003-9
1871:10.1007/978-0-8176-4953-1_13
1769:Introduction of Graph Theory
1402:Eulerian trails are used in
340:strongly connected component
2579:Encyclopedia of Mathematics
2027:Proc. 52-nd MFTI Conference
633:Choose any starting vertex
99:Seven Bridges of Königsberg
2616:
1619:– a path that visits each
1509:Undirected Eulerian graphs
811:Counting Eulerian circuits
511:{\displaystyle O(|E|^{2})}
271:such that, at each vertex
2503:T. van Aardenne-Ehrenfest
2284:10.1007/978-1-4612-0619-4
2210:10.1137/S0036144595295272
2134:SIAM Journal on Computing
1536:It is possible to have a
1166:complete bipartite graphs
621:
405:
97:while solving the famous
2005:and Robert W. Robinson,
1901:, 2nd ser. (in French),
1627:Route inspection problem
1532:Directed Eulerian graphs
898:Markov chain Monte Carlo
470:bridge-finding algorithm
384:Haus vom Nikolaus puzzle
2408:; Vázsonyi, E. (1938),
2338:10.1137/1.9781611973679
1703:Graph Theory, 1736–1936
361:at most one vertex has
263:of an undirected graph
2067:10.1073/pnas.171285098
1590:
1582:
1560:
1525:
1479:of vertices and edges.
1443:
1388:
1155:
902:Kotzig transformations
807:
758:
721:
720:{\displaystyle O(|E|)}
622:Hierholzer's algorithm
612:
512:
464:. If we are to re-run
454:
453:{\displaystyle O(|E|)}
402:
54:
46:
2532:10.1145/335305.335345
2461:Mathematische Annalen
2430:10.1002/sapm193817159
1664:non-self-intersecting
1588:
1580:
1558:
1551:Mixed Eulerian graphs
1523:
1441:
1389:
1156:
928:and Robinson (1995):
770:
759:
722:
613:
513:
455:
377:
52:
33:
2595:Graph theory objects
2526:, pp. 343–350,
2171:J. Comput. Syst. Sci
2099:Roy, Kuntal (2007).
1767:Jun-ichi Yamaguchi,
1175:
935:
881:and generalized the
738:
692:
526:
476:
425:
261:Eulerian orientation
2275:Modern graph theory
2118:10.2498/cit.1000731
2058:2001PNAS...98.9748P
1424:de Bruijn sequences
1406:to reconstruct the
883:de Bruijn sequences
872:matrix tree theorem
757:{\displaystyle |E|}
314:connected component
136:. This is known as
2474:10.1007/BF01442866
1814:10.1007/BF02579193
1591:
1583:
1561:
1526:
1444:
1434:In infinite graphs
1384:
1151:
924:was determined by
918:asymptotic formula
900:approach, via the
808:
773:Hamiltonian cycles
754:
717:
681:doubly linked list
608:
508:
450:
411:Fleury's algorithm
406:Fleury's algorithm
403:
301:strongly connected
297:strong orientation
77:that visits every
55:
47:
39:Königsberg Bridges
2399:. Translated as
2347:978-1-61197-366-2
2052:(17): 9748–9753.
1972:978-0-444-89110-5
1855:Tarjan, Robert E.
1611:Handshaking lemma
1361:
1306:
1280:
1222:
1128:
1090:
1045:
1032:
1004:
989:
816:Complexity issues
243:and "cycle" with
206:, also called an
43:Five room puzzles
16:(Redirected from
2607:
2542:
2499:(1883), 257–261.
2484:
2452:Hierholzer, Carl
2447:(1736), 128–140.
2432:
2415:
2398:
2393:(in Hungarian),
2388:
2379:Weiszfeld, Endre
2358:
2357:
2355:
2354:
2323:
2306:
2304:
2266:
2260:
2258:
2240:Erdös centennial
2228:
2222:
2221:
2193:
2187:
2186:
2166:
2160:
2159:
2149:
2129:
2123:
2122:
2120:
2096:
2090:
2089:
2079:
2069:
2037:
2031:
2030:
2022:
2016:
2000:
1994:
1983:
1977:
1975:
1952:
1946:
1944:
1918:Tarjan, R. Endre
1914:
1908:
1906:
1890:
1884:
1883:
1859:Woods, Donald R.
1847:
1834:
1832:
1808:(3–4): 375–380,
1790:
1784:
1778:
1772:
1765:
1759:
1758:
1730:
1721:
1715:
1698:
1683:
1652:
1633:Veblen's theorem
1617:Hamiltonian path
1606:Five room puzzle
1600:Eulerian matroid
1503:
1499:
1495:
1491:
1484:
1474:
1468:
1461:
1428:de Bruijn graphs
1393:
1391:
1390:
1385:
1380:
1379:
1370:
1369:
1362:
1354:
1332:
1331:
1325:
1324:
1309:
1308:
1307:
1299:
1283:
1282:
1281:
1273:
1262:
1261:
1247:
1246:
1234:
1230:
1223:
1215:
1202:
1201:
1160:
1158:
1157:
1152:
1147:
1146:
1137:
1136:
1129:
1121:
1099:
1098:
1092:
1091:
1086:
1054:
1048:
1047:
1046:
1038:
1033:
1028:
1027:
1026:
1013:
1006:
1005:
997:
991:
990:
985:
968:
956:
955:
806:
801:
794:
787:
763:
761:
760:
755:
753:
745:
726:
724:
723:
718:
713:
705:
617:
615:
614:
609:
604:
596:
576:
568:
560:
559:
547:
539:
517:
515:
514:
509:
504:
503:
498:
489:
459:
457:
456:
451:
446:
438:
364:
360:
228:connected graphs
208:Eulerian circuit
189:undirected graph
138:Euler's Theorem:
130:connected graphs
83:Eulerian circuit
21:
2615:
2614:
2610:
2609:
2608:
2606:
2605:
2604:
2585:
2584:
2563:
2516:
2507:N. G. de Bruijn
2450:
2413:
2400:
2391:Mat. Fix. Lapok
2386:
2375:Grünwald, Tibor
2369:
2366:
2361:
2352:
2350:
2348:
2325:
2324:
2309:
2294:
2268:
2267:
2263:
2230:
2229:
2225:
2195:
2194:
2190:
2168:
2167:
2163:
2156:10.1137/0214061
2147:10.1.1.465.8898
2131:
2130:
2126:
2098:
2097:
2093:
2039:
2038:
2034:
2024:
2023:
2019:
2001:
1997:
1985:Brightwell and
1984:
1980:
1973:
1954:
1953:
1949:
1916:
1915:
1911:
1892:
1891:
1887:
1881:
1849:
1848:
1837:
1792:
1791:
1787:
1779:
1775:
1766:
1762:
1747:10.1137/0128070
1728:
1723:
1722:
1718:
1699:
1695:
1691:
1686:
1653:
1646:
1642:
1596:
1553:
1534:
1511:
1501:
1497:
1493:
1489:
1482:
1472:
1466:
1459:
1436:
1400:
1345:
1310:
1284:
1253:
1248:
1235:
1213:
1209:
1187:
1173:
1172:
1112:
1055:
1049:
1018:
1014:
1007:
992:
969:
963:
947:
933:
932:
922:complete graphs
914:
904:(introduced by
818:
813:
805:
780:
736:
735:
690:
689:
624:
551:
524:
523:
493:
474:
473:
468:'s linear time
423:
422:
419:graph traversal
408:
401:
372:
362:
350:
344:directed cycles
309:
235:directed graphs
177:
134:Carl Hierholzer
28:
23:
22:
15:
12:
11:
5:
2613:
2611:
2603:
2602:
2600:Leonhard Euler
2597:
2587:
2586:
2583:
2582:
2570:
2562:
2561:External links
2559:
2558:
2557:
2550:C. A. B. Smith
2543:
2518:Thorup, Mikkel
2514:
2500:
2493:
2492:, Paris, 1921.
2486:
2448:
2434:
2424:(1–4): 59–75,
2418:J. Math. Phys.
2365:
2362:
2360:
2359:
2346:
2307:
2292:
2270:Bollobás, Béla
2261:
2232:Komjáth, Peter
2223:
2204:(4): 605–629.
2188:
2177:(2): 214–230.
2161:
2140:(4): 862–874.
2124:
2091:
2032:
2017:
1995:
1978:
1971:
1947:
1928:(6): 160–161,
1909:
1885:
1879:
1835:
1785:
1773:
1760:
1741:(4): 876–880.
1716:
1692:
1690:
1687:
1685:
1684:
1643:
1641:
1638:
1637:
1636:
1630:
1624:
1614:
1608:
1603:
1595:
1592:
1552:
1549:
1538:directed graph
1533:
1530:
1510:
1507:
1506:
1505:
1486:
1480:
1477:countable sets
1470:
1448:infinite graph
1435:
1432:
1404:bioinformatics
1399:
1396:
1395:
1394:
1383:
1378:
1373:
1368:
1365:
1360:
1357:
1352:
1348:
1344:
1341:
1338:
1335:
1330:
1323:
1320:
1317:
1313:
1305:
1302:
1297:
1294:
1291:
1287:
1279:
1276:
1271:
1268:
1265:
1260:
1256:
1251:
1245:
1242:
1238:
1233:
1229:
1226:
1221:
1218:
1212:
1208:
1205:
1200:
1197:
1194:
1190:
1186:
1183:
1180:
1162:
1161:
1150:
1145:
1140:
1135:
1132:
1127:
1124:
1119:
1115:
1111:
1108:
1105:
1102:
1097:
1089:
1085:
1082:
1079:
1076:
1073:
1070:
1067:
1064:
1061:
1058:
1052:
1044:
1041:
1036:
1031:
1025:
1021:
1017:
1010:
1003:
1000:
995:
988:
984:
981:
978:
975:
972:
966:
962:
959:
954:
950:
946:
943:
940:
913:
910:
832:, named after
817:
814:
812:
809:
804:
803:
796:
789:
781:
752:
748:
744:
716:
712:
708:
704:
700:
697:
677:
676:
669:
654:
623:
620:
607:
603:
599:
595:
591:
588:
585:
582:
579:
575:
571:
567:
563:
558:
554:
550:
546:
542:
538:
534:
531:
507:
502:
497:
492:
488:
484:
481:
449:
445:
441:
437:
433:
430:
407:
404:
400:
399:
396:
393:
390:
387:
379:
371:
368:
367:
366:
347:
328:
325:
317:
308:
305:
246:directed cycle
204:Eulerian cycle
181:Eulerian trail
176:
173:
153:Eulerian graph
149:
148:
145:if and only if
115:
114:
95:Leonhard Euler
87:Eulerian cycle
63:Eulerian trail
26:
24:
14:
13:
10:
9:
6:
4:
3:
2:
2612:
2601:
2598:
2596:
2593:
2592:
2590:
2580:
2576:
2575:
2571:
2568:
2565:
2564:
2560:
2555:
2551:
2547:
2544:
2541:
2537:
2533:
2529:
2525:
2524:
2519:
2515:
2512:
2508:
2504:
2501:
2498:
2494:
2491:
2487:
2483:
2479:
2475:
2471:
2467:
2463:
2462:
2457:
2453:
2449:
2446:
2443:
2439:
2435:
2431:
2427:
2423:
2420:(in German),
2419:
2411:
2407:
2403:
2396:
2392:
2384:
2380:
2376:
2372:
2368:
2367:
2363:
2349:
2343:
2339:
2335:
2331:
2330:
2322:
2320:
2318:
2316:
2314:
2312:
2308:
2303:
2299:
2295:
2293:0-387-98488-7
2289:
2285:
2281:
2277:
2276:
2271:
2265:
2262:
2257:
2253:
2249:
2245:
2241:
2237:
2233:
2227:
2224:
2219:
2215:
2211:
2207:
2203:
2199:
2192:
2189:
2184:
2180:
2176:
2172:
2165:
2162:
2157:
2153:
2148:
2143:
2139:
2135:
2128:
2125:
2119:
2114:
2110:
2106:
2102:
2095:
2092:
2087:
2083:
2078:
2073:
2068:
2063:
2059:
2055:
2051:
2047:
2043:
2036:
2033:
2028:
2021:
2018:
2014:
2013:
2012:Combinatorica
2008:
2004:
2003:Brendan McKay
1999:
1996:
1992:
1988:
1982:
1979:
1974:
1968:
1964:
1960:
1959:
1951:
1948:
1943:
1939:
1935:
1931:
1927:
1923:
1919:
1913:
1910:
1904:
1900:
1896:
1889:
1886:
1882:
1880:9780817649531
1876:
1872:
1868:
1864:
1860:
1856:
1852:
1851:Pólya, George
1846:
1844:
1842:
1840:
1836:
1831:
1827:
1823:
1819:
1815:
1811:
1807:
1803:
1802:Combinatorica
1799:
1795:
1794:Schrijver, A.
1789:
1786:
1782:
1777:
1774:
1770:
1764:
1761:
1756:
1752:
1748:
1744:
1740:
1736:
1735:
1727:
1720:
1717:
1713:
1712:0-19-853901-0
1709:
1705:
1704:
1697:
1694:
1688:
1681:
1677:
1673:
1669:
1665:
1661:
1657:
1651:
1649:
1645:
1639:
1634:
1631:
1628:
1625:
1623:exactly once.
1622:
1618:
1615:
1612:
1609:
1607:
1604:
1601:
1598:
1597:
1593:
1587:
1579:
1575:
1572:
1568:
1566:
1557:
1550:
1548:
1545:
1542:
1539:
1531:
1529:
1522:
1518:
1515:
1508:
1487:
1481:
1478:
1471:
1469:is connected.
1465:
1464:
1463:
1457:
1453:
1449:
1440:
1433:
1431:
1429:
1425:
1421:
1417:
1413:
1409:
1405:
1397:
1381:
1366:
1363:
1358:
1355:
1350:
1346:
1339:
1336:
1333:
1321:
1318:
1315:
1311:
1303:
1300:
1295:
1292:
1289:
1285:
1277:
1274:
1269:
1266:
1263:
1258:
1254:
1249:
1243:
1240:
1236:
1231:
1227:
1224:
1219:
1216:
1210:
1206:
1198:
1195:
1192:
1188:
1181:
1178:
1171:
1170:
1169:
1167:
1148:
1133:
1130:
1125:
1122:
1117:
1113:
1106:
1103:
1100:
1087:
1080:
1077:
1074:
1065:
1062:
1059:
1050:
1042:
1039:
1034:
1029:
1023:
1019:
1015:
1008:
1001:
998:
993:
986:
979:
976:
973:
964:
960:
952:
948:
941:
938:
931:
930:
929:
927:
923:
919:
912:Special cases
911:
909:
907:
903:
899:
895:
891:
886:
884:
880:
875:
873:
869:
865:
864:arborescences
861:
859:
854:
852:
847:
845:
842:van Aardenne-
839:
837:
831:
830:
825:
824:
815:
810:
802:
797:
795:
790:
788:
783:
782:
778:
777:Eulerian path
774:
769:
765:
746:
733:
728:
706:
695:
687:
682:
674:
670:
667:
663:
659:
655:
652:
648:
644:
640:
636:
632:
631:
630:
628:
619:
597:
589:
586:
583:
580:
577:
569:
561:
556:
552:
548:
540:
529:
521:
520:Thorup (2000)
500:
490:
479:
471:
467:
463:
439:
428:
420:
415:
412:
397:
394:
391:
388:
385:
381:
380:
376:
369:
358:
354:
348:
345:
341:
337:
333:
329:
326:
322:
318:
315:
311:
310:
306:
304:
302:
298:
294:
290:
286:
282:
278:
274:
270:
266:
262:
257:
255:
250:
248:
247:
242:
241:
240:directed path
236:
231:
229:
225:
221:
217:
213:
209:
205:
200:
198:
197:semi-eulerian
194:
190:
186:
182:
174:
172:
170:
169:semi-Eulerian
165:
161:
156:
154:
146:
142:
141:
140:
139:
135:
131:
127:
124:
120:
112:
108:
104:
103:
102:
100:
96:
92:
88:
84:
80:
76:
72:
68:
67:Eulerian path
64:
60:
51:
44:
40:
36:
32:
19:
2573:
2556:48: 233–237.
2522:
2513:28: 203–217.
2511:Simon Stevin
2496:
2489:
2468:(1): 30–32,
2465:
2459:
2444:
2441:
2436:Euler, L., "
2421:
2417:
2406:Grünwald, T.
2394:
2390:
2364:Bibliography
2351:. Retrieved
2328:
2274:
2264:
2239:
2226:
2201:
2197:
2191:
2174:
2170:
2164:
2137:
2133:
2127:
2111:(1): 85–92.
2108:
2104:
2094:
2049:
2045:
2035:
2026:
2020:
2010:
1998:
1981:
1957:
1950:
1925:
1921:
1912:
1902:
1898:
1888:
1862:
1805:
1801:
1788:
1776:
1763:
1738:
1732:
1719:
1701:
1696:
1679:
1675:
1671:
1667:
1663:
1659:
1655:
1620:
1573:
1569:
1565:mixed graphs
1562:
1546:
1543:
1535:
1527:
1516:
1512:
1452:Cayley graph
1445:
1408:DNA sequence
1401:
1398:Applications
1163:
915:
906:Anton Kotzig
901:
889:
887:
876:
857:
850:
843:
835:
829:BEST theorem
827:
821:
819:
776:
729:
678:
665:
661:
657:
650:
646:
642:
638:
634:
625:
418:
416:
410:
409:
292:
288:
280:
272:
268:
264:
260:
258:
251:
244:
238:
232:
223:
219:
211:
207:
203:
201:
196:
192:
184:
180:
178:
168:
163:
157:
152:
150:
137:
116:
86:
82:
73:in a finite
66:
62:
59:graph theory
56:
2546:W. T. Tutte
2488:Lucas, E.,
2198:SIAM Review
1680:closed walk
894:#P-complete
868:determinant
686:linear time
355:) − (
283:equals the
254:multigraphs
193:traversable
35:Multigraphs
2589:Categories
2574:Euler tour
2371:Erdõs, Pál
2353:2022-08-19
1689:References
1416:logic gate
890:undirected
627:Hierholzer
417:While the
353:out-degree
336:out degree
324:component.
307:Properties
212:Euler tour
185:Euler walk
175:Definition
18:Euler tour
2482:119885172
2402:Erdős, P.
2397:: 129–140
2218:0036-1445
2142:CiteSeerX
1905:: 257–261
1672:open walk
1367:ϵ
1351:−
1319:−
1290:−
1286:π
1264:−
1225:−
1182:
1134:ϵ
1118:−
1063:−
1016:−
994:π
942:
879:bijective
870:, by the
673:connected
590:
584:
578:⋅
562:
549:⋅
357:in-degree
332:in degree
285:outdegree
256:as well.
224:unicursal
151:The term
2454:(1873),
2381:(1936),
2272:(1998),
2234:(2013),
2086:11504945
1993:", 2004.
1830:13708977
1796:(1983),
1662:to mean
1594:See also
846:hrenfest
823:digraphs
277:indegree
220:Eulerian
187:, in an
37:of both
2302:1633290
2256:3203602
2054:Bibcode
1987:Winkler
1942:0349483
1822:0729790
1755:2100368
1676:circuit
462:bridges
382:As the
69:) is a
2540:128282
2538:
2480:
2344:
2300:
2290:
2254:
2216:
2144:
2084:
2074:
1969:
1963:X.1–13
1940:
1877:
1828:
1820:
1753:
1710:
1670:or an
1621:vertex
1446:In an
466:Tarjan
359:) = 1,
321:cycles
275:, the
183:, or
126:degree
119:proved
117:Euler
109:(or a
91:vertex
2536:S2CID
2478:S2CID
2414:(PDF)
2387:(PDF)
2173:. 2.
2077:55524
1826:S2CID
1751:JSTOR
1729:(PDF)
1678:or a
1668:trail
1660:cycle
1640:Notes
1492:from
1420:trees
926:McKay
838:ruijn
732:deque
216:cycle
111:cycle
75:graph
71:trail
61:, an
2548:and
2505:and
2342:ISBN
2288:ISBN
2214:ISSN
2082:PMID
1967:ISBN
1875:ISBN
1708:ISBN
1658:and
1656:path
1563:All
1475:has
1412:CMOS
860:utte
855:and
853:mith
334:and
233:For
123:even
107:path
79:edge
65:(or
41:and
2577:at
2528:doi
2470:doi
2440:",
2426:doi
2334:doi
2280:doi
2244:doi
2206:doi
2179:doi
2152:doi
2113:doi
2072:PMC
2062:doi
1989:, "
1930:doi
1867:doi
1810:doi
1743:doi
916:An
834:de
587:log
581:log
553:log
287:of
279:of
259:An
222:or
210:or
202:An
195:or
179:An
164:not
160:odd
85:or
57:In
2591::
2534:,
2476:,
2464:,
2458:,
2422:17
2416:,
2404:;
2395:43
2389:,
2377:;
2373:;
2340:.
2310:^
2298:MR
2296:,
2286:,
2252:MR
2250:,
2238:,
2212:.
2202:39
2200:.
2175:48
2150:.
2138:14
2136:.
2109:15
2107:.
2103:.
2080:.
2070:.
2060:.
2050:98
2048:.
2044:.
2009:,
1965:,
1938:MR
1936:,
1924:,
1897:,
1873:,
1857:;
1853:;
1838:^
1824:,
1818:MR
1816:,
1804:,
1800:,
1749:.
1739:28
1737:.
1731:.
1647:^
1430:.
1179:ec
1168::
1043:12
1040:11
939:ec
848:,
840:,
727:.
688:,
303:.
249:.
199:.
171:.
2581:.
2569:.
2530::
2485:.
2472::
2466:6
2445:8
2433:.
2428::
2356:.
2336::
2305:.
2282::
2259:.
2246::
2220:.
2208::
2185:.
2181::
2158:.
2154::
2121:.
2115::
2088:.
2064::
2056::
1976:.
1945:.
1932::
1926:2
1907:.
1903:2
1869::
1833:.
1812::
1806:3
1783:.
1771:.
1757:.
1745::
1714:.
1502:S
1498:S
1494:G
1490:S
1483:G
1473:G
1467:G
1460:G
1382:.
1377:)
1372:)
1364:+
1359:2
1356:1
1347:n
1343:(
1340:O
1337:+
1334:1
1329:(
1322:1
1316:n
1312:n
1304:2
1301:1
1296:+
1293:n
1278:2
1275:1
1270:+
1267:n
1259:2
1255:n
1250:2
1244:n
1241:2
1237:!
1232:)
1228:1
1220:2
1217:n
1211:(
1207:=
1204:)
1199:n
1196:,
1193:n
1189:K
1185:(
1149:.
1144:)
1139:)
1131:+
1126:2
1123:1
1114:n
1110:(
1107:O
1104:+
1101:1
1096:(
1088:2
1084:)
1081:1
1078:+
1075:n
1072:(
1069:)
1066:2
1060:n
1057:(
1051:n
1035:+
1030:2
1024:2
1020:n
1009:e
1002:2
999:1
987:2
983:)
980:1
977:+
974:n
971:(
965:2
961:=
958:)
953:n
949:K
945:(
858:T
851:S
844:E
836:B
800:e
793:t
786:v
751:|
747:E
743:|
715:)
711:|
707:E
703:|
699:(
696:O
666:u
662:u
658:u
651:w
647:w
643:v
639:v
635:v
606:)
602:|
598:E
594:|
574:|
570:E
566:|
557:3
545:|
541:E
537:|
533:(
530:O
506:)
501:2
496:|
491:E
487:|
483:(
480:O
448:)
444:|
440:E
436:|
432:(
429:O
351:(
316:.
293:G
289:v
281:v
273:v
269:G
265:G
20:)
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
