$\require{cancel}\newcommand\degree{^{\circ}} \newcommand\Ccancel[black]{\renewcommand\CancelColor{\color{#1}}\cancel{#2}} \newcommand{\alert}{\boldsymbol{\color{magenta}{#1}}} \newcommand{\blert}{\boldsymbol{\color{blue}{#1}}} \newcommand{\bluetext}{\color{blue}{#1}} \delimitershortfall-1sp \newcommand\abs{\left|#1\right|} \newcommand{\lt}{<} \newcommand{\gt}{>} \newcommand{\amp}{&}$

## Section15.3Chapter 15 Exercises

### SubsectionSection 15.1 Homework

1. To deliver mail in a particular neighborhood, the postal carrier needs to walk along each of the streets with houses (the dots). See Graph A of Figure15.19. Create a graph with edges showing where the carrier must walk to deliver the mail.

2. Suppose that a town has 7 bridges as pictured in Graph B of Figure15.19. Create a graph that could be used to determine if there is a path that crosses all bridges once.

3. The table in Figure15.20 below shows approximate driving times (in minutes, without traffic) between five cities in the Dallas area. Create a weighted graph representing this data.

4. Identify the bridges (if any) in each of the graphs in Figure15.21.

5. Draw a graph to fit each of the descriptions below. Label each vertex. Then for each graph, provide the following information: (i) next to each vertex, write its degree; (ii) give the total number of edges; (iii) give the total number of components.

• a. It has at least 7 vertices and exactly one bridge.
• b. It has at least six edges and at least two components.
• c. It has exactly four vertices each of degree 3.
• d. It is connected and has five vertices, exactly one of which has degree 1. Does your graph have any bridges?
• e. It is connected and has five vertices, all of which have degree 2. Does this graph have any bridges?

### SubsectionSection 15.2 Homework

6. For each of the graphs in Figure15.22 below, if one exists, find an Euler circuit or an Euler path. If an Euler circuit or path do not exists, explain why.