Editing Eulerian path (section)

{{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'''.