1.2.1. Proof of Correctness

Try these first

1. 1.

   What is an Euler Circuit?

   Hint

   Think about what makes a path closed.

2. 2.

   How many vertices can have an odd degree in an Euler Path?

   Hint

   Remember the conditions for Euler paths.

3. 3.

   What is a necessary condition for an Euler circuit?

   • All vertices have odd degrees
   • All vertices have even degrees
   • Two vertices have odd degrees

   Hint

   Think about the degrees of the vertices.

4. 4.

   True or False: Fleury's Algorithm should always avoid cut edges.

   • True
   • False

   Hint

   Recall the 'not burning bridges' concept.

5. 5.

   Construct a graph with exactly two vertices of odd degree and demonstrate finding an Euler path.

   Hint

   Focus on how you connect the odd-degree vertices.

6. 6.

   Using Fleury's Algorithm, analyze a provided graph step by step to find the Euler circuit.

   Hint

   Ensure you prioritize non-cut edges first.