  We consider the minimum spanning tree problem with predictions, using the
weight-arrival model, i.e., the graph is given, together with predictions for
the weights of all edges. Then the actual weights arrive one at a time and an
irrevocable decision must be made regarding whether or not the edge should be
included into the spanning tree. In order to assess the quality of our
algorithms, we define an appropriate error measure and analyze the performance
of the algorithms as a function of the error. We prove that, according to
competitive analysis, the simplest algorithm, Follow-the-Predictions, is
optimal. However, intuitively, one should be able to do better, and we present
a greedy variant of Follow-the-Predictions. In analyzing that algorithm, we
believe we present the first random order analysis of a non-trivial online
algorithm with predictions, by which we obtain an algorithmic separation. This
may be useful for distinguishing between algorithms for other problems when
Follow-the-Predictions is optimal according to competitive analysis.
