2.4.3. Unique Path Property

Try these first

1. 1.

   What is a Minimum Cost Spanning Tree?

   Hint

   Think about how these trees are formed and what they contain.

2. 2.

   How many edges does a tree with n vertices contain?

   Hint

   Consider how removing an edge impacts the connectivity of a tree.

3. 3.

   What is the primary objective of a Minimum Cost Spanning Tree?

   • To connect all vertices with the fewest edges
   • To minimize the total edge weight
   • To create a cycle

   Hint

   Think about the keyword 'minimum' in the context of costs.

4. 4.

   True or False: A spanning tree can have cycles.

   • True
   • False

   Hint

   Consider the properties that define a tree.

5. 5.

   Given a graph with vertices A, B, C, and D and edges (A-B, 3), (A-C, 4), (B-D, 5), (C-D, 1), determine the Minimum Cost Spanning Tree and justify your edges.

   Hint

   Consider the edge weights carefully before selecting.

6. 6.

   Construct an acyclic graph with 8 vertices and demonstrate the unique path property between any two vertices.

   Hint

   Draw out the graph and label the paths clearly.