Graph Theory Vocab Test Review

Which vertices are adjacent to E?

• B and C

• B, C, D, and A

• B

• A, B, C, D, F, G

Tags

CCSS.6.G.A.4

Which is an example of a disconnected graph?

• 
• 
• 
• 
• None are disconnected graphs

Choose all vertices that are adjacent to vertex A. Select all that apply.

• B

• C

• D

• E

What is the degree of vertex B?

• 1

• 2

• 3

• 4

• 5

What is the chromatic number of this graph?

• 4

• 3

• 5

• 8

Classes A to H need a final exam schedule. The graph shows classes connected by an edge if they share a student in common. Based on the coloring, which classes can be scheduled at the same time? (Select ALL that apply.)

• A, B, E

• A, F, H

• C, F

• H, G, D

• F, D, H

Graphs that contain Euler Circuits have...

• 0 odd vertices.

• 1 odd vertex.

• 2 odd vertices.

• more than 2 odd vertices.

A Hamilton Circuit must touch every __________ once and only once

• Vertex

• Edge

• Loop

• Degree

Which of the following is an example of a Hamilton Circuit starting at A?

• AGCBA

• ABCDEFDCGA

• ABCGFED

• AGFEDCBA

What is the only algorithm that is guaranteed to give an optimal Hamilton circuit?

• brute-force method

• nearest neighbor method

• kruskal's algorithm

• fleury's algorithm