Suppose $k$ is a positive integer. The Degree$-$Constrained Spanning Tree Problem asks:

Given a graph, is it possible to create a spanning tree such that the degree of each vertex is less than or equal to $k?$

Describe how you could create a verifier that will verify a solution in polynomial time as a function of the number of vertices. Justify why it works in polynomial time and why it satisfies the definition of a verifier.

Solution: