WordWalk Puzzles and Graph Theory

WordWalk puzzles are word games based on the directed graphs inherent in the spelling of words (in any language that supports alphabetical spelling).  The idea is that the sequence of letters in each word implies a unique directed graph that is unique for the given word.  Letters are assigned unique vertices in the graph and the relation 'is-followed-by' between letters is reflected in a directed graph edge.

For example, the word 'jump' would be represented as the graph <V,E> where V={j,u,m,p} and E={(j,u),(u,m),(m,p)}.

Pictorially, we might have:

(The special diamond shape for the letter 'u' is used in official WordWalk puzzles to indicate that this letter is a vowel.)

This directed graph contains only a single path and is perhaps not very interesting because each letter occurs exactly once.  But if a letter occurs more than once, an arrow is drawn from the letter just before the repeat back to the original node for that latter.  E.g.,in the word 'elevated', the 'e' occurs three times.  Its graph is:

Of course, if we have a double letter, like the 'o' in 'good', we would get a self-loop:

So far, so good.  But what if we build these directed graphs out of more than one word, so that there are connected paths for each of these words in a single graph that contains them both (the union of these two graphs)?  Let's try 'good' and 'dog':

Since the associated sets of letters in 'good' and 'dog' are the same, the only thing that is now different are some new arrows for 'dog'.  But what if we chose another word that only has some letters in common with the previous two, say, the word 'done'?  

The topology and the number of paths can get wild in a hurry!  

The WordWalk puzzles build graphs in the following way:  A list of words is chosen that are unknown to the puzzle solver. These are called 'root words'.  Next, a number of subwords of these words is chosen. A subword is a word that contains only letters that also belong to the root words. 'dog' is a thus a subword of 'good'.   The graph is beefed up with additional edges based on the sequences of letters in the subwords and the final graph is presented to the user, usually presenting the nodes for vowels as diamonds and also giving the user the first letters of each of the root words.

These puzzles can get very hard very fast!

Here's one based on the root word 'another', presented as a puzzle to be solved:

It includes the clue words (subwords) 'throat', 'near', and 'rate' (which you must try to find in the graph).  Can you solve it?

You can a lot more at wordwalk.net.  There you'll find some free puzzle books to download.

Enjoy!