Non-trivial runs of Prim's algorithm What does it mean when we say that a run of Prim's algorithm is trivial? What are example graphs for either case, that is with and without trivial runs?
Prim's algorithm greedily chooses the smallest edge leaving the set of already connected nodes (until all nodes are connected).

It is not clear what "non-trivial run" means here; I propose this: a run of Prim is trivial if in every step, it can choose the smallest available edge. This would happen on linear chains, for instance.

With this "definition", a non-trivial run is one during which the algorithm can not choose a cheap edge because it would create a cycle, but has to take a more expensive one. Here is an example graph:


[source]

If you start the algorithm with $A$, edge $\{B,C\}$ would be the cheapest after having chosen $\{A,B\}$ and $\{A,C\}$, but it can not be chosen.