• :00Days
• :00Hours
• :00Mins
• 00Seconds
A new era for learning is coming soon Suggested languages for you:

Europe

Answers without the blur. Sign up and see all textbooks for free! Q44SE

Expert-verified Found in: Page 805 ### Discrete Mathematics and its Applications

Book edition 7th
Author(s) Kenneth H. Rosen
Pages 808 pages
ISBN 9780073383095 # Find a minimum spanning tree of each of these graphs where the degree of each vertex in the spanning tree does not exceed 2. 1. Therefore, the resulting minimum spanning tree is given in the graph shown below. 2. Therefore, the resulting minimum spanning tree is given in the graph shown below. See the step by step solution

## Step 1: General form

Definition of tree: A tree is a connected undirected graph with no simple circuits.

Definition of Circuit: It is a path that begins and ends in the same vertex.

Minimum spanning tree: A spanning tree with smallest possible sum of weights of its edges.

## Step 2: (a) Evaluate the minimum spanning tree of the given graph

Given that, a graph is shown below. Noticed that the edges with the smallest weight 1 are $$\left\{ {b,c} \right\}$$ and $$\left\{ {b,d} \right\}$$.

Since, both edges cannot be included, because we will need a degree of more than 2 to connect to a, f or e.

So, we can only include one of the edges.

For example, let us use $$\left\{ {b,c} \right\}$$, then we will also have to use $$\left\{ {c,d} \right\}$$ to connected to d.

Then we need to connect b to another vertex (a, e, or f). we shouldn’t connect b to f as the weight on $$\left\{ {b,c} \right\}$$ is the largest weight of an edge incident to b. we can choose among the other two vertices.

For example, let us choose $$\left\{ {a,b} \right\}$$.

At last, noticed that $$\left\{ {a,f} \right\}$$ and $$\left\{ {e,f} \right\}$$ have to be in the minimum spanning tree. Because the graph either connected or contains a vertex with degree more than 2.

The resulting minimum spanning tree is given in the graph shown below. Conclusion: The above graph represents the possibility of spanning tree.

## Step 3: (b) Evaluate the minimum spanning tree of the given graph

Given that, a graph is shown below. Noticed that a is only connected t b, so $$\left\{ {a,b} \right\}$$ has to be included in the graph.

Then, use at most one more edge incident to b.

We cannot use the edges with weight 1,4 and 5. Because we will require the use of three edges incident to g, to d, to e or to g.

We should use the edge of weight 2, which is $$\left\{ {b,c} \right\}$$.

We cannot use any more edges incident to b. so, we have to include the edges $$\left\{ {c,d} \right\}$$ and $$\left\{ {d,g} \right\}$$.

Since, $$\left\{ {e,g} \right\}$$ has a weight that is the sum of the weight of $$\left\{ {e,f} \right\}$$ and $$\left\{ {f,g} \right\}$$, we should include the two edges.

So, the resulting minimum spanning tree is given in the graph shown below. Hence, the above graph represents the possibility of spanning tree. ### Want to see more solutions like these? 