1.2. Fleury’s Algorithm

Try these first

1. 1.

   Define an Euler circuit.

   Hint

   Think about what it means for a path to return to its start.

2. 2.

   What is the required degree for all vertices in a graph to have an Euler circuit?

   Hint

   Consider the connectivity of edges at each vertex.

3. 3.

   What condition must a graph satisfy to have an Euler circuit?

   • At least one vertex with odd degree
   • All vertices with even degree
   • Only one vertex

   Hint

   Consider the connections at each vertex.

4. 4.

   True or False: Fleury's Algorithm can be used on graphs with disconnected vertices.

   • True
   • False

   Hint

   Recall the definition of connected graphs.

5. 5.

   Consider a graph with 5 vertices where vertex degrees are as follows: A-2, B-3, C-2, D-1, E-1. Analyze its properties regarding Euler paths and circuits.

   Hint

   Count the degree of vertices to see which are odd.

6. 6.

   Construct a unique graph that allows for multiple Euler circuits. Describe your reasoning and show your construction.

   Hint

   Think about how many edges connect each vertex.