Question

a graph is given to the right
a. explain why the graph has at least one euler path
b. use trial and error or fleurys algorithm to find one such path

a. choose the correct explanation below.
a. it has more than two odd vertices.
b. it has exactly two even vertices.
c. it has exactly two odd vertices.
d. all graphs have at least one euler path

Explanation:

According to Euler's theorem, a graph has an Euler path if and only if it is connected and has exactly 0 or 2 odd - degree vertices.

Part a

• Option A: If a graph has more than two odd vertices, it does not have an Euler path. So, option A is incorrect.
• Option B: The number of even vertices is not the criterion for the existence of an Euler path. The relevant property is the number of odd vertices. So, option B is incorrect.
• Option C: By Euler's theorem, a connected graph with exactly two odd vertices has an Euler path. So, option C is correct.
• Option D: Not all graphs have an Euler path. For example, a graph with three odd vertices does not have an Euler path. So, option D is incorrect.

Part b

Let's find an Euler path. The odd vertices are \(B\) and \(C\).
Start at \(B\).

• \(B

ightarrow A
ightarrow D
ightarrow E
ightarrow A
ightarrow E
ightarrow C
ightarrow D
ightarrow C\)

Answer:

a

C. It has exactly two odd vertices

b

\(B - A - D - E - A - E - C - D - C\) (Note: There are other possible Euler paths, for example \(B - A - E - D - A - D - C - E - C\))