Answer to Question #128042 in Discrete Mathematics for Muhammad Danyal

Question

Q2 Draw any three graphs (Take help from book, but DO NOT copy paste any graph from examples or exercise. Your graphs must be random and all must neither be euler nor all non-euler) (2+1+2+2)
a) Figure out Euler graph from these three graphs.
b) Write down the Euler path of these graphs.
c) If not Euler, provide the reason.

Answer 1

Let's give a few definitions and make some calculations to answer our questions.

Degree of a vertex is a number of edges which are incident to it.

Counting degree for all vertices of all 3 graphs we receive next information:

Graph 1:

deg(1) = 1

deg(2) = 4

deg(3) = 6

deg(4) = 4

deg(5) = 3

Graph 2:

deg(1) = 2

deg(2) = 4

deg(3) = 2

deg(4) = 4

deg(5) = 2

Graph 3:

deg(1) = 1

deg(2) = 3

deg(3) = 3

deg(4) = 2

deg(5) = 3

An Euler graph is a graph for which all vertices are of even degree.

An Euler cycle is a path which starts and ends at the same graph vertex and uses each graph edge exactly once.

Euler's Theorem.

A connected graph has an Euler cycle if and only if every vertex has even degree.

a) Figure out Euler graph from these three graphs.

b) Write down the Euler path of these graphs.

c) If not Euler, provide the reason.

From here we can say that (a) graph 2 is Euler graph with (b) Euler cycle 1-2-3-4-2-4-5-1.

According to Euler's Theorem (c) graph 1 is non-Euler graph, because it doesn't have Euler cycle (as deg(1)=1 and deg(5)=3). (But it has Euler path 1-2-3-2-3-4-3-5-4-5, and such graph is called semi-Euler graph).

And (c) graph 3 is also non-Euler graph, because it doesn't have Euler cycle (as deg(1) = 1, deg(2) = 3, deg(3) = 3 and deg(5) = 3).