Editing Eulerian path (section)

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