Share
Explore BrainMass

Randomly Eulerian Graphs

Recall that a graph G is randomly Eulerian from a vertex x if and maximal trail starting at x in an Euler circuit. (If T = xx_1 ... x_l, then T is a maximal trail starting at x iff x_l is an isolated vertex in G - E(T).) Prove that a nonempty graph G is randomly Eulerian from x iff G has an Euler circuit and x is contained in every cycle of G.

Solution Preview

Proof that a nonempty graph G is randomly Eulerian from vertex V if and only if G has an Euler circuit (G is an Eulerian graph) and V is contained in every cycle of G.

(1) Direction "if":
From contradiction:
Suppose G is an Eulerian graph and vertex V is contained in every cycle of G but V is not randomly Eulerian.
Then there is a non-Eulerian ...

Solution Summary

Randomly Eulerian Graphs are investigated. The solution is detailed and well presented. The response received a rating of "5/5" from the student who originally posted the question.

$2.19