TOPICS
Search

Eulerian Orientation


An Eulerian orientation of a finite graph that is undirected is a graph orientation in which every graph vertex has equal indegree and outdegree (Finch 2003, p. 412). Multiple edges are oriented individually. A graph loop contributes one to both the indegree and outdegree and contributes two to the vertex degree.

A finite graph that is undirected admits an Eulerian orientation iff every graph vertex has even vertex degree. Necessity follows because the vertex degree is the sum of the equal indegree and outdegree. For sufficiency, orient an Eulerian cycle in each connected component that contains a graph edge. Isolated vertices require no directions. An Eulerian orientation of a connected graph with at least one graph edge is an Eulerian digraph.

The cycle graph C_n, for n>=3, has two Eulerian orientations, one in each direction around the graph cycle. A graph with no edges has one Eulerian orientation.


See also

Eulerian Digraph, Eulerian Graph, Graph Orientation, Lieb's Square Ice Constant, Twenty-Vertex Entropy Constant

Explore with Wolfram|Alpha

References

Finch, S. R. "Lieb's Square Ice Constant." §5.24 in Mathematical Constants. Cambridge, England: Cambridge University Press, pp. 412-413, 2003.

Cite this as:

Weisstein, Eric W. "Eulerian Orientation." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/EulerianOrientation.html

Subject classifications