Suppose we are given a weighted connected undirected graphGwhere every vertex is colored either red orblack, and we want to find a spanning tree where no edge is between two vertices of the same color (we callsuch an edgemonochromatic). Describe an algorithm which either finds such a tree of least total weight ordetermines that none exists (e. g. if all vertices have the same color). Give a short argument for why youralgorithm is correct.