Graph Theory Intro

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.

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.

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

a. Will this graph have an Euler Circuit? Why or why not?

b. Will it have a Hamilton Circuit? Why or why not?

(both parts - 0.5 pt yes/no, 0.5 pt for why/why not)

Scenario: The Mayor's daughter is getting married and they having been arguing over the dinner seating arrangement for the 12 couples not sitting at the head table because of all the conflicts between couples.

The Mayor gives you the sheet of paper shown, listing the couples (using single letters instead of names to protect their identities) and their various conflicts. He then asks you to let him know how many tables will be needed, and which couples will be sitting where.

How many tables will be needed, and which couples (A-L) can sit where?

Assume the members of each couple will sit together - you aren't trying to keep the members of any single couple apart, just the members of different couples.

(3 pts total; graph = 1 pts, # of tables needed = 1 pt, correct seating chart equals full credit).

Which set represents the vertices of the graph?

• {1,2}, {2,3}. {2,4}, {4,5}, {4,6}

• {1, 2, 3, 4, 5, 6,}

• {1, 2, 3, 4, 5, 6, 7}

• {1,2}, {2,3}. {2,4}, {4,5}, {4,6}, {6,7}

Table shows the vertices and the sum of degrees of a graph.

Calculate the number of edges of the graph.

• 6

• 8

• 16

• 32

Choose all vertices that are adjacent to vertex A

• B

• C

• D

• E

Which of the following is not a path from D to A/

• DCA

• DEDCCA

• DCCA

• DECDA

• All of the above are paths from D to A