In graph-based parsing finding the max spanning tree given sentence (S) and graph (G) a spanning tree over a G is a subset of G that is a tree covering all the vertices in G, thus a spanning tree over G that starts from the root is a valid parse of S. Resultingly, the highest score is the maximum spanning tree.