Editing Eulerian path (section)

== 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.