Chapter 7 Review

Which of the four graphs pictured below are trees?

• Graph 2
• Graph 2, 4
• Graph 2, 3
• Graph 2,3,4

Which of the four graphs pictured below are not trees?

• Graph 3
• Graph 2, 4
• Graph 2, 3
• Graph 1,3

The number of vertices in a tree with 12 edges is 

• 10
• 11
• 12
• 13

Assume graph G has no loops or multiple edges. Which of the following graphs are definitely trees?

• G has 9 vertices and 8 bridges 
• G has 11 vertices and 9 edges
• G has 7 vertices and no circuits
• All graphs are trees

The number of edges in a tree with 32 vertices is 

• 30
  30
• 31
• 32
• 33

Suppose a graph has 15 vertices and 14 edges. Then

• Graph must be a tree
• G is either a tree or its not connected
• G cannot have any circuits 
• G cannot have more than one path joining any two vertice

How many spanning trees does the graph have?

• 3
• 4
• 5
• 8

Using Kruskal’s algorithm, which edge should you choose second?

• AE
• BD
• DE
• AB

Using Kruskal’s algorithm, which edge should you choose fourth?

• AB
• BC
• BD
• DE

Find the minimum spanning tree using Kruskal’s algorithm and provide the overall weight of the MST. 

• 240
• 7
• 280
• 220