Discrete Math Final Exam Review: Graph Theory

Which statement is true of the graph shown?

• The graph contains Euler paths.

• The graph contains Euler circuits.

• The graph contains both Euler paths and Euler circuits.

• The graph does not contain any Euler paths or Euler circuits.

The vertex set, V, and edge set, E, of a particular graph are given below.

V = {T, U, V, W, X, Y, Z}

E = {TV, TY, UY, UY, VV, VX, WY, XZ, XZ}

Which of the following statements is true of the graph?

• The graph contains only even vertices.

• Vertex V is adjacent to exactly three vertices.

• There is exactly one bridge in the graph.

• Edge XZ is adjacent to exactly one other edge.

Apply the nearest neighbor algorithm to the weighted graph 4 times, each time starting with a different vertex.

What is the weight of the Hamilton circuit, or circuits, that produce the smallest weight?

What is the weight of the Hamilton circuit produced by generating the cheapest-link algorithm?

*Edges labeled with a weight of "0" do not exist.

What is the redundancy of the network shown?

In the graph shown, the vertices represent towns, and the edges represent scenic highways connecting the towns.

Lucille wants to start at her hometown, town A, travel each of the scenic highways exactly once, and then return to town A.

Which statement below is true of this scenario?

• Lucille will be able to accomplish exactly what she wants.

• Lucille can travel along each highway exactly once, but she won't be able to start and end at town A.

• There is no way for Lucille to travel along each highway once without having to travel the same highway again to return home.

• Lucille does not have enough information to know whether or not this can be done.

What is the weight of the minimum spanning tree in the graph shown?

The results of a round-robin chess tournament are recorded in the complete graph shown. Which statement is true of the tournament?

• There was a definitive winner of the tournament without having to use a tie-breaker.

• There was a two-way tie for first place.

• There was a three-way tie for first place.

• There was a five-way tie for first place.

Which of the following trips in the graph is a path with a length of 4?

• A, B, D, C, A

• E, D, C, E, D

• C, A, E, C, D

• A, B, C, D, E, B

What is the chromatic number of the graph shown?