### Chapter Test

For the following Exercises, use the figure shown.

1
.

Name the edges in Graph

*T*.2
.

Identify the graph(s) with six edges.

For the following exercises, use the figure shown.

3
.

Identify any of the graphs that is a subgraph of Graph

*D*.4
.

Identify any graphs with no cyclic subgraphs of any size.

5
.

Consider Graph 4 and Graph 6 in the given figure. Determine if one graph is a subgraph of the other. If so, give a correspondence between vertices that demonstrates this relationship. If not, identify conflicting characteristics.

6
.

For the following exercise, use Graph

*A*in the given figure. Consider each sequence of vertices. Determine if it is only a walk, both a walk and a path, both a walk and a trail, all three, or none of these.*d*→*e*→*b*→*c*→*f*7
.

For the following exercise, use Graphs

*A*and*K*in Figure 12.369. Determine the chromatic number of Graph*K*. Give a coloring that supports your conclusion.For the following exercise, use the graphs and multigraphs in the given figure.

8
.

Identify any graphs and/or multigraphs that are not Eulerian. If there are none, state so.

9
.

List the set of vertices for each component in Graph 11.

10
.

Find an Euler circuit beginning and ending at vertex

*b*in Graph 12 if one exists.11
.

Use Fleury’s algorithm to construct an Euler trail for the given graph beginning at vertex

*f*of your choice.12
.

Use the graphs shown to determine whether the sequence of vertices

*d*→*b*→*c*→*f*→*e*→*d*is a Hamilton cycle, an Euler circuit, both, or neither.13
.

Calculate the number of distinct Hamilton cycles in a complete graph with 15 vertices.

14
.

Use the figure shown to find the weight of the given Hamilton cycle:

*t*→*w*→*x*→*u*→*y*→*v*→*s*→*r*→*q*→*t*For the following exercises, use this information: For the Halloween celebration at an elementary school, the students from Classroom

*I*will visit every classroom once and return to their own classroom. The floor plan of the school is given.15
.

Draw a graph to represent the classrooms of the elementary school in which each vertex is a classroom and an edge between two vertices indicates that there is a path between the two rooms that does not pass the door to another classroom.

16
.

Use your graph to find a Hamilton circuit beginning and ending at

*I*.17
.

Explain what the Hamilton circuit you found represents for the students in Classroom

*I*.18
.

Find a Hamilton cycle of low weight for Graph 18, beginning at vertex

*q*, and using the nearest neighborhood method. What is the weight of the cycle?19
.

Use Kruskal’s Algorithm to find a minimum spanning tree for the below graph. Graph the tree and give its weight.