Solution to Q2 Draw any three graphs (Take help from book, but DO NOT copy paste any … - Sikademy
Author Image

Archangel Macsika

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) 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.

The Answer to the Question
is below this banner.

Can't find a solution anywhere?

NEED A FAST ANSWER TO ANY QUESTION OR ASSIGNMENT?

Get the Answers Now!

You will get a detailed answer to your question or assignment in the shortest time possible.

Here's the Solution to this Question

Draw any three graphs (let's take 3 graphs from next picture).



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).

Related Answers

Was this answer helpful?

Join our Community to stay in the know

Get updates for similar and other helpful Answers

Question ID: mtid-5-stid-8-sqid-3845-qpid-2544