1. Euler circuit: A circuit that uses every edge in a graph once and only once

2. a.

   b. An Euler circuit can’t be found because there are vertices with odd valence.

   c. Eulerize the graph. 

3. (b) In the real life context, the added edges represent streets that will be traversed twice when following the Euler circuit. This is why edges can only be added where there are already existing edges.

4. a. Not an Euler circuit because it doesn’t use every edge – ec is missed.

   b. Not an Euler circuit because it doesn’t use every edge only once – cd is used twice.

   c. Not an Euler circuit because it isn’t a circuit – it doesn’t start and end at the same vertex.

5. Find a good Eulerization for the following graph. Note that this is only one of many possibilities.

6.  a. The valence of B is 3 which is not even. Therefore, the graph does not have an Euler Circuit.

    b. The tour marked by wiggly edges is a Hamilton circuit.

7. A graph that represents the floor plan is shown below  

It is not possible. In order for Bobby to visit each doorway of the house exactly once, and end up outside again, he needs to find an Euler circuit for the above graph. Since the valence of A is 3, the graph doesn’t have any Euler circuit.

To find a route where he revisits doorways as few time as possible, Bobby needs to draw more route(s) between the vertexes so that all vertexes have even degrees. The number of adding routes must also as few as possible. Since each point A, B, D, E has valence 3. Bobby needs to add at least two more routes. For instance, he can add a route between A and B and a route between D and E as in the following figure. 
Now he can find an Euler circuit for this new graph. This circuit must also start at O and end at O to fulfill his requirement. One of possible circuits is: OABCEDBADEO