Chapter Review

Determine the number of vertices in Graph S.

Identify the graph with the fewest edges.

Name the vertices in Graph U.

Identify any pairs of vertices in Graph S that are not adjacent.

Which graphs only has vertices of degree 2?

Identify the graph in which the sum of the degrees of the vertices is 16.

Amazon.com has a network of warehouses that are used to move packages around the United States. Delivery trucks from warehouse deliver packages to other locations. These mail trucks also pick up packages to bring back to their home warehouse. Explain how a graph or multigraph might be drawn to model this scenario by identifying the objects that could be represented by vertices and the connections that could be represented by edges. Indicate whether a graph or a multigraph would be a better model.

Eduardo has two groups of four friends, group A and group B. Within each group, each of the members of the group are friends with each other but not with those in the other group. The individuals in group A have no other friends, but the individuals in group B each has their own group of four friends, and the individuals within those groups are all friends with each other, but with no one outside their own group. Draw a graph to represent the given scenario.

Explain why Graph B is not a subgraph of Graph C.

Identify any graphs that have a quadrilateral cyclic subgraph and name the vertices.

Identify a clique in Graph C by listing its vertices.

Draw a graph with the following characteristics: largest clique has 4 vertices, a pentagonal cyclic subgraph, exactly two vertices of degree 4.

How many edges are in a complete graph with 12 vertices?

How many triangles are in a complete graph with 11 vertices?

Identify three differences between Graph 1 and Graph 2 that demonstrate the graphs are not isomorphic.

Determine if Graph 3 is isomorphic to Graph 4. If so, identify a correspondence between the vertices which demonstrates the isomorphism. If not, identify at least two characteristics that verifies this.

Determine if Graph 3 is isomorphic to Graph 5. If so, identify a correspondence between the vertices that demonstrates the isomorphism. If not, identify a characteristic that verifies this.

Consider Graph 4 and Graph 5. 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.

Draw the complements of Graphs 7 and 9. Determine whether the graphs you drew are isomorphic to each other and explain how you know. Use this information to determine whether Graphs 7 and 8 are isomorphic.

Draw the complements of Graphs 7 and 10. Determine whether the graphs you drew are isomorphic to each other and explain how you know. Use this information to determine whether Graphs 7 and 10 are isomorphic.

Draw the complements of Graphs 8 and 9. Determine whether the graphs you drew are isomorphic to each other and explain how you know. Use this information to determine whether Graphs 8 and 9 are isomorphic.

e → d → b → e → f

e → b → d → e → f → c → b → d

e → f → b → d

n → o → q → n → p → m → n

m → n → o → q → n → p → o → n → m

p → o → q → n → m → p

Are Graphs A and K planar graphs? What does your answer tell you about the chromatic number of each graph?

How many vertices are in the largest complete subgraph of Graph A? What does this tell you about the chromatic number of Graph A?

Create a coloring of Graph A, which uses exactly four colors, or explain why it is not possible.

Create a coloring of Graph K, which uses exactly two colors, or explain why it is not possible.

Determine the chromatic number of Graph A. Give a coloring that supports your conclusion.

Determine the chromatic number of Graph K. Give a coloring that supports your conclusion.

connected

disconnected

Eulerian

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

Determine whether the sequence of edges represents an Euler circuit in Multigraph 15:
K → L → N → M → O → S → T → Q → U → P → R

Find an Euler circuit beginning and ending at vertex g in Graph 12 if one exists. Otherwise, explain how you know such an Euler circuit does not exist.

Give an example of a pair of edges that could be duplicated to eulerize Multigraph 14.

Exactly two vertices of odd degree

Has an Euler trail

Has exactly one local bridge

Determine whether the sequence of edges, A → B → C → H → G → D → F → E, is an Euler trail, an Euler circuit, or neither for the graph. If it is neither, explain why.

Suppose that an edge were added to Graph 11 between vertices s and w. Determine if the graph would have an Euler trail or an Euler circuit, and find one.

A student has been asked to use Fleury’s algorithm to construct an Euler trail in the given graph. The student decides to begin the trail at vertex d. Is this a good choice, why or why not?

A student who is using Fleury’s algorithm to construct an Euler trail has decided to begin with f → d → a → b → …. If the student is off to a good start, help the student by completing the Euler trail. If the student has made an error, explain the error.

Use Fleury’s algorithm to construct an Euler trail for Graph 16 beginning at the vertex of your choice.

Graph F. a → b → e → c → b → d → c → a

Graph K. m → n → q → o → p → m

Graph A. b → d → e → f → c → b → e

$\left(n-<!--\; -\; -->1\right)!,n=12$

$\left(n-<!--\; -\; -->1\right)!,n=14$

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

q → t → w → x → u → y → v → s → r → q

w → x → y → u → v → s → r → q → t → w

Graph A. e → b → c → f → e → b → e

Graph A. b → c → f → e → d → b → e

Graph K. n → q → o → p → m

Graph K. o → q → m → n → p

Vertices a and e.

Vertices d and f.

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

Use your graph to find a route that the principal can take beginning at the Front Office in room A, visiting each room exactly once (without passing by another room), and ending at room F, which is next to the exit.

Would the route you found be best to trace out a Hamilton path, an Euler trail, both, or neither in the graph you drew? Explain how you know.

A lumber distributor is loading pallets onto trucks with the intention of using the fewest trucks possible to send a shipment. The distributor loads the pallets with the greatest length that will fit on the truck first and continues loading until no more pallets will fit. Then the next truck is loaded using the same approach.

A traveler wants to visit five cities by airplane. The traveler lists all the possible orders in which the cities can be visited then calculates the best airfare for each itinerary and selects the least expensive option.

Graph 17, vertex a

Graph 18, vertex m

Graph 18; vertex m

Graph 17; vertex a

Graph 18 vertex m

Graph 17, vertex a

The products at a particular factory are manufactured in phases. The same equipment is utilized for each phase, but it must be formatted differently to accomplish different tasks. The transition time to convert between a format for one task and another task varies. The times are given in the table below.

Use the table to draw a graph in which the vertices represent tasks A, C, D, F, and G, and the weights of the edges indicate the times in minutes to transition between pairs of tasks. Use the nearest neighbor method to find an order in which to complete tasks A, C, D, F, and G, which keeps the transition times down and ends with the same set up as it began so that the factory is ready start the next batch. Assume that there are no restrictions on which tasks can be completed in which order. Hint: The nearest neighbor algorithm may give a different result depending on which vertex is the starting vertex; so, you must check all possibilities.

A tree with eight vertices, exactly two of degree three.

A connected graph with eight vertices, exactly two of degree 3, which is not a tree.

Graph 19

Graph 20

Three spanning trees of Graph A, which include both edges be and de.

Three spanning trees of Graph K, which include edges mn and oq, but do not include no.

Graph 17

Graph 18