3.6.1: Exercises

Use Graphs A, B, C, D, E, F, G, H, and I to answer the following exercises. Identify any graph or graphs with the given characteristics or indicate that none do.

Exercise \(\PageIndex{1}\)

Connected

Exercise \(\PageIndex{2}\)

Disconnected

Exercise \(\PageIndex{3}\)

Exactly two components

Exercise \(\PageIndex{4}\)

Exactly three components

Exercise \(\PageIndex{5}\)

Exactly four components

Exercise \(\PageIndex{6}\)

Exactly five components

Exercise \(\PageIndex{7}\)

At least one vertex of odd degree

Exercise \(\PageIndex{8}\)

All vertices of even degree

Exercise \(\PageIndex{9}\)

An Euler circuit

Exercise \(\PageIndex{10}\)

A path between vertex j and each other vertex on the same graph

Use the graphs in the previous exercise to answer the following exercises. For each exercise, list the set of vertices for each component in the given graph.

Exercise \(\PageIndex{11}\)

Graph B

Exercise \(\PageIndex{12}\)

Graph E

Exercise \(\PageIndex{13}\)

Graph F

Exercise \(\PageIndex{14}\)

Multigraph I

Use the graphs in the initial exercise to answer the following exercises. For each exercise, a graph and a vertex on the graph are given. Find a path between the given vertex and each other vertex on the graph. If this is not possible, indicate that it is not.

Exercise \(\PageIndex{15}\)

Graph A, vertex c.

Exercise \(\PageIndex{16}\)

Graph B, vertex m.

Exercise \(\PageIndex{17}\)

Graph D, vertex x.

Exercise \(\PageIndex{18}\)

Graph F, vertex w.

Exercise \(\PageIndex{19}\)

Graph G, vertex a.

Exercise \(\PageIndex{20}\)

Graph H, vertex e.

Use the graphs in the initial exercise to answer the following exercises. For each exercise, a graph and a vertex on the graph are given. Find an Euler circuit beginning and ending at the given vertex if one exists. If no Euler circuits exist, explain how you know that they do not.

Exercise \(\PageIndex{21}\)

Graph A, vertex c.

Exercise \(\PageIndex{22}\)

Graph B, vertex k.

Exercise \(\PageIndex{23}\)

Graph D, vertex w.

Exercise \(\PageIndex{24}\)

Graph G, vertex b.

Exercise \(\PageIndex{25}\)

Graph H, vertex o.

Exercise \(\PageIndex{26}\)

Multigraph I, vertex p.

For the following exercises, use the connected graphs. In each exercise, a graph is indicated. Determine if the graph is Eulerian or not and explain how you know. If it is Eulerian, give an example of an Euler circuit. If it is not, state which edge or edges you would duplicate to eulerize the graph.

Exercise \(\PageIndex{27}\)

Graph J

Exercise \(\PageIndex{28}\)

Graph K

Exercise \(\PageIndex{29}\)

Multigraph L

Exercise \(\PageIndex{30}\)

Graph M

Exercise \(\PageIndex{31}\)

The figure shows a map of zoo exhibits A through P with walkways shown in gray. Draw a graph, or multigraph, to represent the routes through the zoo in which the edges represent walkways and the vertices represent turns and intersections, which are each marked with a star. Notice that there is exactly one exhibit between each pair of adjacent vertices. Label the edges with the corresponding exhibit. Use it to determine if it is possible for a visitor to begin at the entrance, view each exhibit exactly once, and end back at the entrance. If it is possible, give an example of a circuit on the graph that would represent a route the visitor could take. If it is not possible, explain why.

The figure shows the map of the exhibits at an indoor aquarium with hallways shown in gray. Turns and intersections of hallways are marked with stars.

Exercise \(\PageIndex{32}\)

Use the Euler circuit theorem and a graph in which the edges represent hallways and the vertices represent turns and intersections to explain why a visitor to the aquarium cannot start at the entrance, visit every exhibit exactly once, and return to the entrance.

Exercise \(\PageIndex{33}\)

Use an eulerization of the graph you found to determine the least amount of backtracking necessary to allow a visitor to begin at the entrance, see every exhibit at least once, and return to the entrance. How many hallways must be covered twice? Explain your reasoning.

The map of the states of Imaginaria is given.

Exercise \(\PageIndex{34}\)

Use a graph to determine if it is possible to travel through Imaginaria crossing each the border between each pair of states exactly once, and returning to the state in which you started.

Exercise \(\PageIndex{35}\)

Use an eulerization of the graph you found to determine the fewest borders that must be covered twice in order to cross each border at least once and return to the state in which you started. Explain your reasoning.