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

Given a simple, connected, weighted and undirected graph $($represented as an adjacency matrix$)$ and an integer $k0,$ is it possible to find a spanning tree with total weight 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: