Honors Discrete 7.1 – 7.3 Review Worksheet:

Notes and Helpful Tips are provided. Use a separate paper!!!

TREE: Connected Graph (Network) with NO Circuits

  • Property #1: Any two vertices have exactly ONE path between them
  • Property #2: All edges in a tree are called bridges.
  • Property #3: Number of Vertices is One More Than Number of Edges
  • REDUDANCY: R = EDGES – VERTICES + 1
  • Redundancy = 0: the original graph is a tree
  • Redundancy > 0 : the original graph is not a tree and need to remove R edges to create a spanning tree

1) Determine if the following graph descriptions will (1) ALWAYS, (2) NEVER, or (3) SOMETIMES be a tree. If the graph is SOMETIMES, then provide an example of the graph as a tree and another not as a tree.

a. 9 vertices and exactly one path between any two different vertices.

b. 12 edges and 10 vertices.

c. 5 vertices and 4 edges.

d. 7 vertices and 6 bridges.

e. 8 vertices and no circuits.

2) Which of the following graphs is a tree?

  1. Calculate the REDUNDANCY for each graph.
  2. Find one SPANNING TREE by highlighting/tracing edges.

3) Draw a tree for each of the following descriptions on the back of this sheet.

  • HINT: Start with the number of vertices you need, and then try to make degree statements work to create a CONNECTED graph with NO CIRCUITS.

  1. 8 Vertices
  1. 6 vertices and one vertex of degree 2.
  1. 5 vertices and one vertex of degree 3.
  1. 7 vertices and one vertex of degree 4 and one of degree 3.

4) Find the total number of spanning trees in each of the below graphs.

  1. Find the length of all the primary circuits in the graph.
  2. BORDER EDGE Case: Multiply the two bordering circuits and then subtract one from that product.
  3. Multiply the lengths of all remaining circuits and special case values.

5) Find the MINIMUM SPANNING TREE in each of the graphs below:

  • Number of Edges in Spanning Tree = Vertices – 1
  • Pick the smallest weights for edges as long as no circuits are created
  • Degree can be any number greater than 0 (NO Degree 2 requirement)

Honors Discrete 7.1 – 7.3 Review Worksheet: SOLUTIONS

1) Determine if the following graph descriptions will (1) ALWAYS, (2) NEVER, or (3) SOMETIMES be a tree. If the graph is SOMETIMES, then provide an example of the graph as a tree and another not as a tree.

a. 9 vertices and exactly one path between any two different vertices.

ALWAYS

b. 12 edges and 10 vertices.

NEVER

c. 5 vertices and 4 edges.

SOMETIMES

d. 7 vertices and 6 bridges.

ALWAYS

e. 8 vertices and no circuits.

SOMETIMES

2) Which of the following graphs is a tree?

  1. Calculate the REDUNDANCY for each graph.
  2. Find one SPANNING TREE by highlighting/tracing edges.

3) Draw a tree for each of the following descriptions on the back of this sheet.

  1. 8 Vertices
  1. 6 vertices and one vertex of degree 2.
  1. 5 vertices and one vertex of degree 3.
  1. 7 vertices and one vertex of degree 4 and one of degree 3.

4) Find the total number of spanning trees in each of the below graphs.

5) Find the MINIMUM SPANNING TREE in each of the graphs below: