# Euler Digraph: Characterization

Not what you're looking for?

Page 90, Theorem 4.6 ( To show that a digraph is hamiltonian if and only if for each vertex v, indegree (v) =outdegree (v)

Page 92 Exercise problem 4.1 ( A modified version of konigsberg problem where, two extra bridges are built. )

Page 93, Figure 4.5 need to show as Hamilton. (Show that dodecahedron is hamiltonian)

See attached file for full problem description.

##### Purchase this Solution

##### Solution Summary

Here we prove the Necessary and sufficient condition for a digraph to be Eulerian. It also solves three problems from Graphs and Digraphs concerning a modified Konigsberg problem and provide a Hamiltonian cycle for dodecahedron.

##### Solution Preview

Problem 4.1 and 4.5, I have attached figures.

Problem 4.1:

-------------

We construct a graph of the present day Konigsberg bridges and see that there are exactly two vertices (A and B) have odd degree. We know that every connected graph with exactly 2 odd vertices have an Eulerian tour starting and ending at these vertices. Hence we can device such a route passing through all the edges. The attached figure shows such a route.

Problem of figure 4.5

--------

We need to show the graph of dodecahedron is Hamiltonian. We do this by providing such a cycle explicitly. In the attached figure, follow the vertex sequence 1,2,3,...,19,20,1 which is such a Hamiltonian cycle.

Theorem 4.6

-------------

Theorem: Let D be a connected non-trivial digraph. D is Eulerian if and

only if id(v) = od(v) for every vertex. (id:in degree, od:out degree).

Proof:

A trail in a graph is a path without repeated edges.

Suppose D is Eulerian. Consider any ...

##### Purchase this Solution

##### Free BrainMass Quizzes

##### Multiplying Complex Numbers

This is a short quiz to check your understanding of multiplication of complex numbers in rectangular form.

##### Exponential Expressions

In this quiz, you will have a chance to practice basic terminology of exponential expressions and how to evaluate them.

##### Solving quadratic inequalities

This quiz test you on how well you are familiar with solving quadratic inequalities.

##### Know Your Linear Equations

Each question is a choice-summary multiple choice question that will present you with a linear equation and then make 4 statements about that equation. You must determine which of the 4 statements are true (if any) in regards to the equation.

##### Geometry - Real Life Application Problems

Understanding of how geometry applies to in real-world contexts