Finding common label sequences in a directed acyclic graph
Can't you just use the graph to build a trie, and then have the counts of all words.  (You would have to augment the trie slightly.)  It's a simple step from there to sort the words by number of occurrences, although the most common word will trivially be the single label that appears the most in your DAG.  (It gets more interesting if you look at most common words of a given length...)