Eulerian Line

graph-theory

Definition

Eulerian Line

A closed edge sequence is called Eulerian line if it contains all edges and vertices of $G=(V,E)$ exactly once.

Criterion

A directed Graph, weakly connected graph $G$ posesses an open Eulerian line if there exists two vertices $v_1,v_2\in V(G)$ such that:

$$\begin{array}{rl}\exists v_1,v_2\in V(G):& d^{+}(v_1)=d^{-}(v_2)+1\\ \wedge & d^{+}(v_2)=d^{-}(v_2)-1\\ \wedge & \forall v_3\in V(G)\setminus \{v_1,v_2\}:d^{+}(v_3)=d^{-}(v_3)\end{array}$$