Graph Theory Test

Which of these is NOT required for two graphs to be isomorphic?

• The two graphs must have the same number of edges, and the same number of vertices, as one another.

• The two graphs must have the same number of vertices of any given degree as one another.

• The top left vertex of the first graph must correspond to the top left vertex of the second graph.

• It must be possible to plug the vertices from the first graph onto the vertices of the 2nd graph with all original connections intact and none added.

How are two objects that are in conflict represented on a graph?

• Two vertices connected by an edge.

• Two vertices not connected by an edge.

• Two edges between the same pair of vertices.

• Two vertices of the same degree.

Tags

CCSS.HSA.CED.A.3

One of the requirements to have an Euler Circuit is to have a connected graph. What is the other requirement?

• No even degree vertices.

• No more than 2 even degree vertices.

• No odd degree vertices.

• No more than two odd degree vertices.

One of the requirements to have an Euler Path is to have a connected graph. What is the other requirement?

• No even degree vertices.

• No more than 2 even degree vertices.

• No odd degree vertices.

• No more than two odd degree vertices.

What is the maximum number of colors required to do a map coloring of a two-dimensional, or planar, map?

• 3

• 4

• 5

• 6

Which of these is a rule of map coloring?

• Different regions cannot be colored the same color.

• Adjacent regions must not be the same color.

• The color pink may not be used.

• Regions that border at a point are considered adjacent.

Which of these is required when drawing a Hamilton Path?

• To start and end at the same point.

• To visit all vertices exactly once.

• To go over every edge on the graph.

• To do an interpretive dance while drawing it.

Which of these statements is accurate regarding a conflict resolution problem?

• The nodes on the graph drawn represent the groupings.

• The edges on the graph drawn represent the objects that need to be grouped.

• After a map coloring is done, the objects that are the same color are objects that were in conflict.

• None of the other answer choices to this question are true statements.

If the numbers represent distance in miles, which one of these routes is longest?

• Town Center-Mountain View-Train Station-

  Best Beach

• Town Center- Train Station- Mountain View- Best Beach

• Town Center- Camp Graffinstuff-

  Best Beach-

  Mega Mall

• Mountain View-Camp Graffinstuff-

  Carnival Wharf-

  Waterfalls

Shown in the image is a representation of the seven bridges of Königsberg, a historically noteworthy math problem that laid the foundations for what became graph theory.

Is it possible to cross all seven bridges exactly once and end up where you started? Why or why not?

Assume that there are no ways to get from one landmass to another bar the use of these seven bridges. Routes can start from any of the four landmasses.

(1 pt yes/no, 2 pts why/why not)