Question

In Exercises 31-33 find a degree-constrained spanning tree of the given graph where each vertex has degree less than or equal to 3, or show that such a spanning tree does not exist.

Short answer

Therefore, the degree-constrained spanning tree of given graph is shown below.

Step-by-step solution

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.

Definition of rooted tree: A rooted tree is a tree in which one vertex has been designated as the root and every edge is directed away from the root.

Degree-constrained spanning tree (Definition): A degree-constrained spanning tree of a simple graph G is a spanning tree with the property that the degree of a vertex in this tree cannot exceed some specified bound. Degree-constrained spanning trees are useful in models of transportation system where the number of roads at an intersection is limited, in communication network models where the number of links is limited entering a node is limited, and so on.

Evaluate the degree-constrained spanning tree

Given that, a graph is shown below.

Evaluate the given graph.

Here, the degree at every vertex can be at most 3.

Let us construct a path in the tree first. If the remaining vertices cannot be attached at the end of the path, we go back to the last vertex of the path by one degree of at most 2 and that connects to one of the remaining vertices.

That is, the graph of the degree-constrained spanning tree is shown below.

Therefore, above graph represents that the vertices of degree-constrained spanning tree.