Share
Explore BrainMass

A Nontrivial Connected Digraph

Prove that a nontrivial connected digraph D is Eulerian if and only if E(D) can be partitioned into subsets E_i , 1<=i<=k, where [E_i] is a cycle for each i.
<= means less and equal.

Please can you explain this step by step and can you draw a graph.

Solution Preview

The proof is explained and illustrated in the attached file.

Eulerian graphs

4.6 prove that a nontrivial connected digraph D is eulerian if and only if E(D) can be partitioned into subsets E_i , 1<=i<=k, where [E_i] is a cycle for each i.
<= means less and equal.

This proof is similar to the proof for question 4.4 in that it uses the same construction for the sequence of paths It might therefore be useful to follow proof 4.4 first, to see whether you come up with the same proof before reading on.

Definitions

As before, a walk of length n in a graph is an alternating sequence:

If each of the edges are distinct we call the walk a path. Also, if we call the walk (or path) closed.

A cycle is a closed path in which all the vertices, except for are distinct. Such a path is also called a simple closed path. The graph of a cycle is called a polygon - an equivalent definition being: a polygon is a finite connected graph that is regular and of degree 2.

A ...

Solution Summary

This is a proof regarding a nontrivial connected digraph.

$2.19