2.4.1. Number of Edges in a Tree

Try these first

1. 1.

   What defines a tree in graph theory?

   Hint

   Think about how trees are different from other graphs.

2. 2.

   If a tree has 7 vertices, how many edges does it have?

   Hint

   Use the formula: n - 1.

3. 3.

   What relationship exists between the number of vertices and edges in a tree?

   • n - 1 edges
   • n + 1 edges
   • n edges

   Hint

   Think about the definition of a tree.

4. 4.

   True or False: A tree can have cycles.

   • True
   • False

   Hint

   Recall the properties of a tree.

5. 5.

   Given a graph with 8 vertices and a total of 12 edges, can it be a tree? Justify your answer.

   Hint

   Use the definition of trees.

6. 6.

   Construct a minimum spanning tree for a weighted graph shown below: (provide a sample graph with weights). Describe how you would apply Prim's Algorithm.

   Hint

   Visualize the steps of adding edges without making a cycle.