6.1. Basic definitions and theorems

A circuit in a graph G containing all the edges is said to be an Euler circuit of G.

An Euler trail contains all edges but it is not closed.

A graph is Eulerian if it has an Euler circuit.

A graph G is defined to be even (odd) graph if all its vertices have even (odd) degree.

Theorem 6.1. A non-trivial connected graph has an Euler circuit iff each vertex has even degree.

Theorem 6.2. A connected graph has an Euler trail from a vertex x to a vertex  iff x and y

are the only vertices of odd degree.

Theorem 6.3. If G is a connected graph with 2k odd vertices ,  then  can be partitioned into subsets  so that for each  is a trail connecting odd vertices and such that at most one of these trails has odd length.

Theorem 6.4. A nontrivial connected graph G is eulerian iff  can be partitioned into subsets , where each subgraph   is a cycle.