Skip to main content
Logo image

Contemporary Mathematics: Contemporary Mathematics at Nebraska

Michelle Homp, Alyssa Seideman, Sean Gravelle, Andrew Hayes, The Mabel Elizabeth Kelly Fund

Section 18.2 Chapter 18 Exercises

Figure 18.2.1.
  1. Which of the graphs in Figure 18.2.1 above are trees? Explain how you know.
  2. Given the descriptions below, decide which of these options applies and explain your choice: (T) the graph is definitely a tree, (N) the graph is definitely not a tree, (M) the graph may or may not be a tree (more information is needed).
    1. A network has 12 vertices and 13 edges.
    2. A network has 12 vertices and 12 edges.
    3. A network has 12 vertices and 12 bridges.
    4. A network has 12 vertices and 11 edges.
    5. A network has 12 vertices and at least 11 edges.
    6. A network has 12 vertices and 11 bridges.
    7. A network has 7 vertices (A through G) and there is only one path connecting A and G.
    8. A network has 7 vertices, all of which have degree 2.
  3. The table below gives the distance (in kilometers) between several cities in Nebraska. Use Kruskal’s algorithm to find a minimal spanning tree for these cities. Draw the tree and give its total weight.
Figure 18.2.2.
PrevTopNext