Honors Discrete 7.1 – 7.3 Worksheet:

USE A SEPARATE SHEET OF PAPER AS NEEDED!!!!

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

a. 5 vertices and exactly one path from any vertex to any other vertex.

b. 27 edges and 26 vertices.

c. 5 vertices and 4 edges.

d. 15 vertices and 14 bridges.

e. 4 vertices and no circuits.

f. 5 bridges and 6 vertices.

g. 3 vertices and no circuits

h. Euler Path Exists

i. Connected graph with Redundancy = 0

j. G is connected with 6 vertices and every vertex has degree 5.

2) Which of the following graphs is a tree?

  • If it is not a tree, create a spanning tree.
  • Hint: Calculate the redundancy and check if it is a network.

3) Draw a tree with each of the following requirements.

  1. 5 vertices and one vertex of degree 2.
  1. 6 vertices and two vertices of degree 3.

  1. 8 vertices and one vertex of degree 4 and one of degree 3.
  1. 7 vertices with two vertices of degree 2.

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: Highlight, Trace, or identify the edges and the total weight.

Honors Discrete 7.1 – 7.3Worksheet: SOLUTIONS

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

a. 5 vertices and exactly one path from any vertex to any other vertex.

b. 27 edges and 26 vertices.

c. 5 vertices and 4 edges.

d. 15 vertices and 14 bridges.

e. 4 vertices and no circuits.

f. 5 bridges and 6 vertices.

g. 3 vertices and no circuits

h. Euler Path Exists

i. Connected graph with Redundancy = 0

j. G is connected with 6 vertices and every vertex has degree 5.

2) Which of the following graphs is a tree?

  • If it is not a tree, create a spanning tree.
  • Hint: Calculate the redundancy and check if it is a network.

#2 continued)

3) Draw a tree with each of the following requirements.

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

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: Highlight, Trace, or identify the edges and the total weight.