Editing Cycle (graph theory) (section)

== Covering graphs by cycle ==
In his 1736 paper on the [[Seven Bridges of Königsberg]],<ref name = Euler>{{cite journal|last = Euler|first = Leonhard|author-link = Leonhard Euler|year=1741|title = Solutio problematis ad geometriam situs pertinentis|journal = Commentarii Academiae Scientiarum Petropolitanae|language = Latin|volume = 8|pages = 128-140 + Plate VIII|url = http://eulerarchive.maa.org/backup/E053.html}} Translated into English as [https://www.cantab.net/users/michael.behrend/repubs/maze_maths/pages/euler_en.html Solution of a problem in the geometry of position], Michael Behrend.</ref> widely considered to be the birth of graph theory,<ref>{{cite journal|last = Räz|first = Tim|year = 2018|title = Euler's Königsberg: The explanatory power of mathematics|journal = European Journal for Philosophy of Science|volume = 8|issue = 3|pages = 331–346|doi = 10.1007/s13194-017-0189-x|s2cid = 125194454| url=http://philsci-archive.pitt.edu/18320/1/main_document_philsci.pdf |quote = Arguably, the fact that Euler’s paper stands at the beginnings of graph theory is its most important innovation.}}</ref><ref>{{cite journal|last = Shields|first = Rob|author-link = Rob Shields|year = 2012|title = Cultural Topology: The Seven Bridges of Königsburg 1736|journal = [[Theory, Culture & Society]]|volume = 29|issue = 4–5|pages = 43–57|doi = 10.1177/0263276412451161|s2cid = 146875675}}</ref> [[Leonhard Euler]] proved that, for a finite undirected graph to have a closed walk that visits each edge exactly once (making it a closed trail), it is necessary and sufficient that it be connected except for isolated vertices (that is, all edges are contained in one component) and have even degree at each vertex.<ref name = Euler/> The corresponding characterization for the existence of a closed walk visiting each edge exactly once in a directed graph is that the graph be [[strongly connected]] and have equal numbers of incoming and outgoing edges at each vertex. In either case, the resulting closed trail is known as an [[Eulerian path|Eulerian trail]]. If a finite undirected graph has even degree at each of its vertices, regardless of whether it is connected, then it is possible to find a set of simple cycles that together cover each edge exactly once: this is [[Veblen's theorem]].<ref>{{Citation | last1=Veblen | first1=Oswald | author1-link=Oswald Veblen | title=An Application of Modular Equations in Analysis Situs | jstor=1967604 | series=Second Series | year=1912 | journal=[[Annals of Mathematics]] | volume=14 | issue=1 | pages=86–94 | doi = 10.2307/1967604 }}.</ref> When a connected graph does not meet the conditions of Euler's theorem, a closed walk of minimum length covering each edge at least once can nevertheless be found in [[polynomial time]] by solving the [[route inspection problem]].

The problem of finding a single simple cycle that covers each vertex exactly once, rather than covering the edges, is much harder. Such a cycle is known as a [[Hamiltonian cycle]], and determining whether it exists is [[NP-complete]].<ref>{{citation
 | author = Richard M. Karp
 | author-link = Richard M. Karp
 | chapter = Reducibility Among Combinatorial Problems
 | chapter-url = http://cgi.di.uoa.gr/~sgk/teaching/grad/handouts/karp.pdf
 | title = Complexity of Computer Computations
 | editor = R. E. Miller and J. W. Thatcher
 | publisher = New York: Plenum
 | pages = 85–103
 | year = 1972
 | access-date = 2014-03-12
 | archive-date = 2021-02-10
 | archive-url = https://web.archive.org/web/20210210182452/http://cgi.di.uoa.gr/~sgk/teaching/grad/handouts/karp.pdf
 | url-status = live
 }}.</ref> Much research has been published concerning classes of graphs that can be guaranteed to contain Hamiltonian cycles; one example is [[Ore's theorem]] that a Hamiltonian cycle can always be found in a graph for which every non-adjacent pair of vertices have degrees summing to at least the total number of vertices in the graph.<ref>{{citation|first=Ø.|last=Ore|author-link=Øystein Ore|title=Note on Hamilton circuits|journal=[[American Mathematical Monthly]]|volume=67|year=1960|page=55|issue=1|jstor=2308928|doi=10.2307/2308928}}.</ref>

The [[cycle double cover conjecture]] states that, for every [[bridgeless graph]], there exists a [[multiset]] of simple cycles that covers each edge of the graph exactly twice. Proving that this is true (or finding a counterexample) remains an open problem.<ref>{{citation
 | last = Jaeger | first = F.
 | contribution = A survey of the cycle double cover conjecture
 | doi = 10.1016/S0304-0208(08)72993-1
 | pages = 1–12
 | series = North-Holland Mathematics Studies
 | title = Annals of Discrete Mathematics 27 – Cycles in Graphs
 | volume = 27
 | year = 1985| isbn = 978-0-444-87803-8
 }}.</ref>