eulerian_circuit (801B)
1 # Eulerian circuit 2 3 A [Eulerian_trail] which is a [cycle_circuit], i.e., starts and ends at the same [vertex] 4 5 An [undirected_graph] has a Eulerian circuit if and only if it is [graph_connected] and the [degree] of each [vertex] is even (this implies in particular that the graph is [bridgeless]) 6 7 If we add forbidden "transitions" aka pairs of incident edges that are not allowed to be consecutive, the [computational_problem] of [deciding] if there is a suitable Eulerian circuit becomes [NP_hard] even if the [degree] of the graph is bounded, specifically for [undirected_graphs] of [maximal_degree] 8 and [directed_graphs] of [maximal_degree] 4, see [dvorak2004eulerian] 8 9 - [Eulerian_circuit_counting] 10 11 Up: [eulerian_path] 12 13 Aliases: Eulerian cycle, Eulerian circuits 14 15 See also: [Veblen's_theorem]