Answer to Question #128040 in Discrete Mathematics for Sana Shayan

Question

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

1.

This graph has an Euler path: 1-3-4-6-5-3-2-7.

It is an Euler graph, because it has an Euler cycle: 1-3-4-6-5-3-2-7-1.

2.

This graph has an Euler path: 1-3-4-6-5-3-2.

It is a non-Euler graph, because it doesn't have an Euler cycle. The reason is vertex 1 has only one adjacent edge. In Euler cycle all vertexes must have even number of adjacent edges.

3.

This graph doesn't have an Euler path, because all vertexes with an odd number of adjacent edges should be either start or finish, so there shouldn't be more than 2 of them. Here are 4 such vetexes.

And accordingly the graph doesn't have an Euler cycle.