# Graph showing valid English words obtained by insertion of single characters

The only other one-letter English word is 'i' (actually 'I'), which would generate its own directed tree graph.

Repeat for different languages (e.g., French, Italian, Spanish, ...).

• That sounds awfully close to a homework I recently gave to my students :) Oct 13 '14 at 21:55
• Please allow me to suggest the following: 1) As you receive help, try to give it too, by answering questions in your area of expertise. 2) Read the faq! 3) When you see good questions and answers, vote them up by clicking the gray triangles, because the credibility of the system is based on the reputation gained by users sharing their knowledge. Also, please remember to accept the answer, if any, that solves your problem, by clicking the checkmark sign! Oct 13 '14 at 21:58
• I doubt anybody will want to answer this if its really a homework for @belisarius' course. Probably if the OP showed some work of his own, and divided the problem into smaller tasks... probably. Oct 14 '14 at 7:04
• @rhermans Oh, I can't know for certain, the concept matches but the text doesn't. In any case that shouldn't refrain anyone from answering. A rant follows: Although I prefer HW questions being addressed in other ways, I don't forbid asking for help and then using it ethically (ie showing what they got as external help and what is their "original" effort). Also, my students are aware that I monitor a few sites because I'm very interested in learning new ways to achieve the HW goals. Oct 14 '14 at 10:13

ClearAll[dL];
dL = Function[{str},
With[{s = Last@str}, Thread[s -> DictionaryLookup[Alternatives @@
(StringExpression @@
StringSplit[StringInsert[s, ".", #],
"." -> LetterCharacter] & /@
Range[1 + StringLength@s])]]], Listable];

edges = DeleteDuplicates@Flatten@Rest@NestList[dL, {"a" -> "a"}, 7];

style = {GraphLayout -> {"RadialEmbedding", "RootVertex" -> "a"},
VertexStyle -> {_ :> White,
(x_ /; StringLength[x] == 8) -> Directive[{Red, PointSize[.01]}],
"a" -> Directive[{Blue, PointSize[.01]}]},
VertexLabels -> {Placed["Name", Tooltip],
(x_ /; StringLength[x] == 8) -> Placed[Style[x, Red, 12], {Tooltip, Before}]},
VertexShapeFunction -> "Point", LabelStyle -> Red,ImageSize -> 700,
EdgeStyle -> Directive[Opacity[.5], Hue[.15, .5, .8]],
Background -> Black, EdgeShapeFunction -> (Line[#1] &) };

gg = Graph[edges, style];
{VertexCount[gg], EdgeCount[gg]}
(*  {2511, 3828} *)

gg


Select[VertexList[gg], StringLength[#] == 8 &]

{"blasters", "blathers", "boasters", "brandied", "brattier", "chanters", "chastens",
"chatters", "chattier", "cheaters", "clatters", "cleansed", "cleanser", "cleanses",
"cleavers", "coasters", "crankier", "cremated", "cremates", "drafters", "draftier",
"flatters", "flattery", "gamblers", "gestated", "gestates", "grafters", "grafting",
"grandeur", "granters", "granting", "gratings", "gyrating", "heathers", "heathery",
"Jeannine", "leathers", "leathery", "loathers", "managers", "martinis", "masterly",
"maximals", "palpated", "palpates", "pastiest", "pastimes", "pastries", "patterns",
"planners", "planters", "platters", "prattled", "prattler", "prelates", "rattlers",
"rattlier", "reflated", "reflates", "relapsed", "relapses", "relaters", "restated",
"restates", "roadster", "roasters", "scantier", "scantily", "shatters", "sheathed",
"sheathes", "slammers", "slathers", "sparkled", "sparsest", "spatters", "splatted",
"splatter", "stampede", "stampers", "staplers", "starkers", "starters", "startled",
"statures", "statuses", "statutes", "strapped", "streamed", "swaddled", "swatches",
"testates", "theaters", "threader", "trampers", "trampled", "trampler", "trappers",


Continuing beyond 7 steps:

laststep =DeleteDuplicates[Last /@ Flatten[dL /@
Thread[1 -> Select[VertexList[gg], StringLength[#] == 8 &]]]

{"cleansers", "splatters", "prattlers", "restarted", "roadsters","stampeded", "stampedes",

DeleteDuplicates[Last /@ Flatten[dL /@ Thread[1 -> laststep]]]
(* {} *)

• The question is purely academic. I feel somehow sorry for all your overwritings +1 :)
– eldo
Oct 15 '14 at 20:58
• @kguler beautiful layout...instructive+1 :) Oct 16 '14 at 1:49
• The initial question stemmed from a problem posted in MIT Technology Review. This final answer is excellent and the layout clear. One teeny improvement would be to allow the user to mouseover a node and have the path from the root ("a") to that selected node become highlighted and each node on the path displayed its word. But such refinements are not needed. Oct 16 '14 at 21:35

I post this (if I understand the question from title and text: single letter addition anywhere in string) to illustrate how unwieldy the graph gets just 3 levels deep. Here just starting with "a".

fun[x_] := With[{c = Characters[x]},
Select[
DictionaryLookup[
StringExpression @@ Riffle[c, ___, {1, 2 Length@c + 1, 2}]],
StringLength@# == StringLength@x + 1 &]]]


Building graph from "a", just for 3 iterations:

gr = NestList[Join @@ fun /@Union[ #[[All, 2]]] &, fun["a"], 3];


Visualizing:

Graph[Join @@ gr]


This would be unwieldy to label/interpret without much cleverer ways to cone down on or render interactive (I look forward to approaches):

The edges for just 2 interations(!):

{"a" -> "ad", "a" -> "ah", "a" -> "am", "a" -> "an", "a" -> "as",
"a" -> "at", "a" -> "ax", "a" -> "fa", "a" -> "ha", "a" -> "la",
"a" -> "ma", "a" -> "pa", "a" -> "ta", "a" -> "ya", "ad" -> "add",
"ah" -> "ash", "ah" -> "bah", "ah" -> "nah", "ah" -> "pah",
"ah" -> "rah", "am" -> "aim", "am" -> "amp", "am" -> "arm",
"am" -> "cam", "am" -> "Cam", "am" -> "dam", "am" -> "ham",
"am" -> "Ham", "am" -> "jam", "am" -> "lam", "am" -> "mam",
"am" -> "Nam", "am" -> "Pam", "am" -> "ram", "am" -> "Sam",
"am" -> "tam", "am" -> "yam", "an" -> "and", "an" -> "ans",
"an" -> "ant", "an" -> "any", "an" -> "awn", "an" -> "ban",
"an" -> "can", "an" -> "Dan", "an" -> "fan", "an" -> "Han",
"an" -> "Ian", "an" -> "Jan", "an" -> "Kan", "an" -> "man",
"an" -> "Man", "an" -> "nan", "an" -> "Nan", "an" -> "pan",
"an" -> "Pan", "an" -> "ran", "an" -> "San", "an" -> "tan",
"an" -> "van", "an" -> "Van", "an" -> "wan", "as" -> "abs",
"as" -> "ads", "as" -> "ans", "as" -> "ash", "as" -> "ask",
"as" -> "asp", "as" -> "ass", "as" -> "gas", "as" -> "has",
"as" -> "mas", "as" -> "pas", "as" -> "was", "at" -> "act",
"at" -> "aft", "at" -> "ant", "at" -> "apt", "at" -> "art",
"at" -> "ate", "at" -> "bat", "at" -> "cat", "at" -> "eat",
"at" -> "fat", "at" -> "hat", "at" -> "mat", "at" -> "Nat",
"at" -> "oat", "at" -> "pat", "at" -> "Pat", "at" -> "rat",
"at" -> "sat", "at" -> "tat", "at" -> "vat", "ax" -> "axe",
"ax" -> "fax", "ax" -> "lax", "ax" -> "Max", "ax" -> "sax",
"ax" -> "Sax", "ax" -> "tax", "ax" -> "wax", "fa" -> "fab",
"fa" -> "fad", "fa" -> "fag", "fa" -> "fan", "fa" -> "far",
"fa" -> "fat", "fa" -> "fax", "fa" -> "fay", "fa" -> "Ufa",
"ha" -> "aha", "ha" -> "had", "ha" -> "hag", "ha" -> "haj",
"ha" -> "ham", "ha" -> "hap", "ha" -> "has", "ha" -> "hat",
"ha" -> "haw", "ha" -> "hay", "la" -> "Ila", "la" -> "lab",
"la" -> "lac", "la" -> "lad", "la" -> "lag", "la" -> "lam",
"la" -> "lap", "la" -> "lav", "la" -> "law", "la" -> "lax",
"la" -> "lay", "la" -> "lea", "la" -> "Ola", "ma" -> "mac",
"ma" -> "mad", "ma" -> "mam", "ma" -> "man", "ma" -> "map",
"ma" -> "mar", "ma" -> "mas", "ma" -> "mat", "ma" -> "maw",
"ma" -> "may", "pa" -> "pad", "pa" -> "pah", "pa" -> "pal",
"pa" -> "pan", "pa" -> "pap", "pa" -> "par", "pa" -> "pas",
"pa" -> "pat", "pa" -> "paw", "pa" -> "pay", "pa" -> "pea",
"pa" -> "spa", "ta" -> "eta", "ta" -> "tab", "ta" -> "tad",
"ta" -> "tag", "ta" -> "tam", "ta" -> "tan", "ta" -> "tap",
"ta" -> "tar", "ta" -> "tat", "ta" -> "tau", "ta" -> "tax",
"ta" -> "tea", "ya" -> "yak", "ya" -> "yam", "ya" -> "yap",
"aid" -> "acid", "aid" -> "aide", "aid" -> "aids", "aid" -> "amid",
"aid" -> "arid", "aid" -> "avid", "aid" -> "laid", "aid" -> "maid",
"aid" -> "paid", "aid" -> "raid", "aid" -> "said", "and" -> "ands",
"and" -> "band", "and" -> "hand", "and" -> "land", "and" -> "Land",
"and" -> "rand", "and" -> "Rand", "and" -> "sand", "and" -> "Sand",
"ash" -> "ashy", "ash" -> "bash", "ash" -> "cash", "ash" -> "Cash",
"ash" -> "dash", "ash" -> "gash", "ash" -> "hash", "ash" -> "lash",
"ash" -> "mash", "ash" -> "Nash", "ash" -> "rash", "ash" -> "sash",
"ash" -> "wash", "ash" -> "Wash", "bah" -> "bahs", "bah" -> "baht",
"bah" -> "bash", "bah" -> "bath", "bah" -> "blah", "pah" -> "path",
"rah" -> "rahs", "rah" -> "rash", "aim" -> "aims", "aim" -> "maim",
"amp" -> "amps", "amp" -> "camp", "amp" -> "damp", "amp" -> "lamp",
"amp" -> "ramp", "amp" -> "tamp", "amp" -> "vamp", "arm" -> "arms",
"arm" -> "army", "arm" -> "arum", "arm" -> "farm", "arm" -> "harm",
"arm" -> "warm", "cam" -> "calm", "cam" -> "came", "cam" -> "camp",
"cam" -> "cams", "cam" -> "clam", "cam" -> "cram", "cam" -> "scam",
"dam" -> "Adam", "dam" -> "dame", "dam" -> "damn", "dam" -> "damp",
"dam" -> "dams", "dam" -> "dram", "dam" -> "Edam", "ham" -> "hams",
"ham" -> "harm", "ham" -> "sham", "ham" -> "wham", "jam" -> "jamb",
"jam" -> "jams", "lam" -> "clam", "lam" -> "Elam", "lam" -> "flam",
"lam" -> "glam", "lam" -> "lama", "lam" -> "lamb", "lam" -> "lame",
"lam" -> "lamp", "lam" -> "lams", "lam" -> "loam", "lam" -> "slam",
"mam" -> "imam", "mam" -> "maim", "mam" -> "mama", "mam" -> "mams",
"ram" -> "cram", "ram" -> "dram", "ram" -> "gram", "ram" -> "pram",
"ram" -> "ramp", "ram" -> "rams", "ram" -> "ream", "ram" -> "roam",
"ram" -> "tram", "Sam" -> "Siam", "Sam" -> "Spam", "tam" -> "tame",
"tam" -> "tamp", "tam" -> "tams", "tam" -> "team", "tam" -> "tram",
"yam" -> "yams", "and" -> "ands", "and" -> "band", "and" -> "hand",
"and" -> "land", "and" -> "Land", "and" -> "rand", "and" -> "Rand",
"and" -> "sand", "and" -> "Sand", "and" -> "wand", "ans" -> "ands",
"ans" -> "ants", "ans" -> "anus", "ans" -> "awns", "ans" -> "bans",
"ans" -> "cans", "ans" -> "Dans", "ans" -> "fans", "ans" -> "Hans",
"ans" -> "Kans", "ans" -> "mans", "ans" -> "nans", "ans" -> "pans",
"ans" -> "sans", "ans" -> "tans", "ans" -> "vans", "ant" -> "ante",
"ant" -> "anti", "ant" -> "ants", "ant" -> "aunt", "ant" -> "cant",
"ant" -> "Kant", "ant" -> "pant", "ant" -> "rant", "ant" -> "want",
"any" -> "many", "any" -> "zany", "awn" -> "awns", "awn" -> "dawn",
"awn" -> "Dawn", "awn" -> "fawn", "awn" -> "lawn", "awn" -> "pawn",
"awn" -> "yawn", "ban" -> "band", "ban" -> "bane", "ban" -> "bang",
"ban" -> "bani", "ban" -> "bank", "ban" -> "bans", "ban" -> "barn",
"ban" -> "bean", "ban" -> "bran", "can" -> "cane", "can" -> "cans",
"can" -> "cant", "can" -> "clan", "can" -> "cyan", "can" -> "scan",
"can" -> "Scan", "Dan" -> "Dana", "Dan" -> "Dane", "Dan" -> "Dans",
"Dan" -> "Dawn", "Dan" -> "Dean", "fan" -> "fain", "fan" -> "fang",
"fan" -> "fans", "fan" -> "faun", "fan" -> "fawn", "fan" -> "flan",
"Han" -> "Hahn", "Han" -> "Hank", "Han" -> "Hans", "Ian" -> "Iran",
"Ian" -> "Ivan", "Jan" -> "Jain", "Jan" -> "Jana", "Jan" -> "Jane",
"Jan" -> "Jean", "Jan" -> "Joan", "Jan" -> "Juan", "Kan" -> "Kane",
"Kan" -> "Kano", "Kan" -> "Kans", "Kan" -> "Kant", "Kan" -> "Kean",
"Kan" -> "Khan", "Kan" -> "Klan", "man" -> "main", "man" -> "mane",
"man" -> "mans", "man" -> "many", "man" -> "mean", "man" -> "moan",
"man" -> "Oman", "Man" -> "Mani", "Man" -> "Mann", "Man" -> "Manx",
"nan" -> "nans", "pan" -> "pain", "pan" -> "pane", "pan" -> "pang",
"pan" -> "pans", "pan" -> "pant", "pan" -> "pawn", "pan" -> "plan",
"pan" -> "span", "pan" -> "Span", "ran" -> "bran", "ran" -> "Bran",
"ran" -> "Fran", "ran" -> "gran", "ran" -> "Iran", "ran" -> "Oran",
"ran" -> "rain", "ran" -> "rand", "ran" -> "rang", "ran" -> "rank",
"ran" -> "rant", "ran" -> "roan", "ran" -> "Tran", "San" -> "Sana",
"San" -> "Sand", "San" -> "Sang", "San" -> "Scan", "San" -> "Sean",
"San" -> "Span", "San" -> "Stan", "tan" -> "Stan", "tan" -> "tang",
"tan" -> "tank", "tan" -> "tans", "tan" -> "tarn", "tan" -> "than",
"van" -> "Evan", "van" -> "Ivan", "van" -> "vain", "van" -> "vane",
"van" -> "vans", "Van" -> "Vang", "wan" -> "swan", "wan" -> "wain",
"wan" -> "wand", "wan" -> "wane", "wan" -> "wank", "wan" -> "want",
"wan" -> "warn", "wan" -> "wean", "abs" -> "albs", "abs" -> "cabs",
"abs" -> "dabs", "abs" -> "gabs", "abs" -> "jabs", "abs" -> "labs",
"abs" -> "Labs", "abs" -> "nabs", "abs" -> "tabs", "ads" -> "adds",
"ans" -> "ants", "ans" -> "anus", "ans" -> "awns", "ans" -> "bans",
"ans" -> "cans", "ans" -> "Dans", "ans" -> "fans", "ans" -> "Hans",
"ans" -> "Kans", "ans" -> "mans", "ans" -> "nans", "ans" -> "pans",
"ans" -> "sans", "ans" -> "tans", "ans" -> "vans", "ash" -> "ashy",
"ash" -> "bash", "ash" -> "cash", "ash" -> "Cash", "ash" -> "dash",
"ash" -> "gash", "ash" -> "hash", "ash" -> "lash", "ash" -> "mash",
"ash" -> "Nash", "ash" -> "rash", "ash" -> "sash", "ash" -> "wash",
"asp" -> "asps", "asp" -> "gasp", "asp" -> "hasp", "asp" -> "rasp",
"asp" -> "wasp", "ass" -> "asks", "ass" -> "asps", "ass" -> "bass",
"ass" -> "Bass", "ass" -> "Kass", "ass" -> "lass", "ass" -> "mass",
"ass" -> "pass", "ass" -> "sass", "ass" -> "Tass", "gas" -> "gabs",
"gas" -> "gads", "gas" -> "gags", "gas" -> "gals", "gas" -> "gaps",
"gas" -> "gars", "gas" -> "gash", "gas" -> "gasp", "gas" -> "gays",
"has" -> "ahas", "has" -> "hags", "has" -> "hams", "has" -> "hash",
"has" -> "hasp", "has" -> "hast", "has" -> "hats", "has" -> "haws",
"has" -> "hays", "mas" -> "macs", "mas" -> "mags", "mas" -> "mams",
"mas" -> "mans", "mas" -> "maps", "mas" -> "mars", "mas" -> "mash",
"mas" -> "mask", "mas" -> "mass", "mas" -> "mast", "mas" -> "mats",
"mas" -> "maws", "mas" -> "Xmas", "pas" -> "pads", "pas" -> "pals",
"pas" -> "pans", "pas" -> "paps", "pas" -> "pars", "pas" -> "pass",
"pas" -> "past", "pas" -> "pats", "pas" -> "paws", "pas" -> "pays",
"pas" -> "peas", "pas" -> "spas", "was" -> "twas", "was" -> "wads",
"was" -> "wags", "was" -> "wars", "was" -> "wash", "was" -> "wasp",
"was" -> "wast", "was" -> "ways", "act" -> "acts", "act" -> "fact",
"act" -> "pact", "act" -> "tact", "aft" -> "daft", "aft" -> "haft",
"aft" -> "raft", "aft" -> "Taft", "aft" -> "waft", "ant" -> "ante",
"ant" -> "anti", "ant" -> "ants", "ant" -> "aunt", "ant" -> "cant",
"ant" -> "Kant", "ant" -> "pant", "ant" -> "rant", "ant" -> "want",
"apt" -> "rapt", "art" -> "arts", "art" -> "arty", "art" -> "Bart",
"art" -> "cart", "art" -> "dart", "art" -> "hart", "art" -> "Hart",
"art" -> "kart", "art" -> "mart", "art" -> "part", "art" -> "tart",
"art" -> "wart", "ate" -> "ante", "ate" -> "ates", "ate" -> "bate",
"ate" -> "date", "ate" -> "fate", "ate" -> "gate", "ate" -> "hate",
"ate" -> "Kate", "ate" -> "late", "ate" -> "mate", "ate" -> "Nate",
"ate" -> "pate", "ate" -> "Pate", "ate" -> "rate", "ate" -> "sate",
"ate" -> "Tate", "bat" -> "baht", "bat" -> "bait", "bat" -> "bast",
"bat" -> "bate", "bat" -> "bath", "bat" -> "bats", "bat" -> "beat",
"bat" -> "boat", "bat" -> "brat", "cat" -> "cant", "cat" -> "cart",
"cat" -> "cast", "cat" -> "cats", "cat" -> "chat", "cat" -> "coat",
"cat" -> "scat", "eat" -> "beat", "eat" -> "east", "eat" -> "eats",
"eat" -> "feat", "eat" -> "heat", "eat" -> "meat", "eat" -> "neat",
"eat" -> "peat", "eat" -> "seat", "eat" -> "teat", "fat" -> "fact",
"fat" -> "fast", "fat" -> "fate", "fat" -> "fats", "fat" -> "feat",
"fat" -> "fiat", "fat" -> "flat", "fat" -> "frat", "hat" -> "chat",
"hat" -> "ghat", "hat" -> "haft", "hat" -> "halt", "hat" -> "hart",
"hat" -> "hast", "hat" -> "hate", "hat" -> "hath", "hat" -> "hats",
"hat" -> "heat", "hat" -> "phat", "hat" -> "shat", "hat" -> "that",
"hat" -> "what", "mat" -> "malt", "mat" -> "mart", "mat" -> "mast",
"mat" -> "mate", "mat" -> "math", "mat" -> "mats", "mat" -> "meat",
"mat" -> "moat", "Nat" -> "Nate", "oat" -> "boat", "oat" -> "coat",
"oat" -> "goat", "oat" -> "moat", "oat" -> "oath", "oat" -> "oats",
"pat" -> "pact", "pat" -> "pant", "pat" -> "part", "pat" -> "past",
"pat" -> "pate", "pat" -> "path", "pat" -> "pats", "pat" -> "peat",
"pat" -> "phat", "pat" -> "prat", "pat" -> "spat", "Pat" -> "Pate",
"rat" -> "brat", "rat" -> "drat", "rat" -> "frat", "rat" -> "prat",
"rat" -> "raft", "rat" -> "rant", "rat" -> "rapt", "rat" -> "rate",
"rat" -> "rats", "sat" -> "salt", "sat" -> "sate", "sat" -> "scat",
"sat" -> "seat", "sat" -> "shat", "sat" -> "slat", "sat" -> "spat",
"sat" -> "swat", "tat" -> "tact", "tat" -> "tart", "tat" -> "tats",
"tat" -> "taut", "tat" -> "teat", "tat" -> "that", "vat" -> "vast",
"vat" -> "vats", "axe" -> "axed", "axe" -> "axes", "axe" -> "axle",
"fax" -> "flax", "lax" -> "flax", "Max" -> "Manx", "Max" -> "Marx",
"tax" -> "taxi", "wax" -> "waxy", "fab" -> "flab", "fad" -> "fade",
"fad" -> "fads", "fag" -> "fags", "fag" -> "fang", "fag" -> "flag",
"fan" -> "fain", "fan" -> "fang", "fan" -> "fans", "fan" -> "faun",
"fan" -> "fawn", "fan" -> "flan", "far" -> "afar", "far" -> "fair",
"far" -> "fare", "far" -> "farm", "far" -> "faro", "far" -> "fear",
"fat" -> "fact", "fat" -> "fast", "fat" -> "fate", "fat" -> "fats",
"fat" -> "feat", "fat" -> "fiat", "fat" -> "flat", "fat" -> "frat",
"fax" -> "flax", "fay" -> "fays", "fay" -> "flay", "fay" -> "fray",
"hag" -> "hang", "hag" -> "shag", "haj" -> "hajj", "ham" -> "hams",
"ham" -> "harm", "ham" -> "sham", "ham" -> "wham", "hap" -> "chap",
"hap" -> "harp", "hap" -> "hasp", "hap" -> "heap", "has" -> "ahas",
"has" -> "hags", "has" -> "hams", "has" -> "hash", "has" -> "hasp",
"has" -> "hast", "has" -> "hats", "has" -> "haws", "has" -> "hays",
"hat" -> "chat", "hat" -> "ghat", "hat" -> "haft", "hat" -> "halt",
"hat" -> "hart", "hat" -> "hast", "hat" -> "hate", "hat" -> "hath",
"hat" -> "hats", "hat" -> "heat", "hat" -> "phat", "hat" -> "shat",
"hat" -> "that", "hat" -> "what", "haw" -> "hawk", "haw" -> "haws",
"haw" -> "Shaw", "haw" -> "thaw", "hay" -> "hays", "hay" -> "hazy",
"hay" -> "shay", "lab" -> "blab", "lab" -> "flab", "lab" -> "labs",
"lab" -> "lamb", "lab" -> "slab", "lac" -> "lace", "lac" -> "lack",
"lag" -> "lags", "lag" -> "slag", "lam" -> "clam", "lam" -> "Elam",
"lam" -> "flam", "lam" -> "glam", "lam" -> "lama", "lam" -> "lamb",
"lam" -> "lame", "lam" -> "lamp", "lam" -> "lams", "lam" -> "loam",
"lam" -> "slam", "lap" -> "clap", "lap" -> "flap", "lap" -> "lamp",
"lap" -> "laps", "lap" -> "leap", "lap" -> "slap", "lav" -> "lava",
"lav" -> "lave", "lav" -> "lavs", "lav" -> "Olav", "lav" -> "Slav",
"law" -> "claw", "law" -> "flaw", "law" -> "lawn", "law" -> "laws",
"law" -> "slaw", "lax" -> "flax", "lay" -> "clay", "lay" -> "Clay",
"lay" -> "flay", "lay" -> "lacy", "lay" -> "lady", "lay" -> "lays",
"lay" -> "lazy", "lay" -> "play", "lay" -> "slay", "lea" -> "flea",
"lea" -> "ilea", "lea" -> "lead", "lea" -> "leaf", "lea" -> "leak",
"lea" -> "lean", "lea" -> "leap", "lea" -> "leas", "lea" -> "plea",
"Ola" -> "Olaf", "Ola" -> "Olav", "Ola" -> "Olga", "mac" -> "mace",
"mad" -> "mead", "mam" -> "imam", "mam" -> "maim", "mam" -> "mama",
"mam" -> "mams", "man" -> "main", "man" -> "mane", "man" -> "mans",
"man" -> "many", "man" -> "mean", "man" -> "moan", "man" -> "Oman",
"map" -> "maps", "mar" -> "mare", "mar" -> "mark", "mar" -> "marl",
"mar" -> "mars", "mar" -> "mart", "mar" -> "Omar", "mas" -> "macs",
"mas" -> "mags", "mas" -> "mams", "mas" -> "mans", "mas" -> "maps",
"mas" -> "mars", "mas" -> "mash", "mas" -> "mask", "mas" -> "mass",
"mas" -> "mast", "mas" -> "mats", "mas" -> "maws", "mas" -> "Xmas",
"mat" -> "malt", "mat" -> "mart", "mat" -> "mast", "mat" -> "mate",
"mat" -> "math", "mat" -> "mats", "mat" -> "meat", "mat" -> "moat",
"maw" -> "maws", "may" -> "many", "may" -> "mayo", "pad" -> "pads",
"pad" -> "paid", "pah" -> "path", "pal" -> "opal", "pal" -> "Opal",
"pal" -> "pail", "pal" -> "pale", "pal" -> "pall", "pal" -> "palm",
"pal" -> "pals", "pal" -> "pawl", "pal" -> "peal", "pan" -> "pain",
"pan" -> "pane", "pan" -> "pang", "pan" -> "pans", "pan" -> "pant",
"pan" -> "pawn", "pan" -> "plan", "pan" -> "span", "pan" -> "Span",
"pap" -> "papa", "pap" -> "paps", "par" -> "pair", "par" -> "para",
"par" -> "pare", "par" -> "park", "par" -> "pars", "par" -> "part",
"par" -> "pear", "par" -> "spar", "pas" -> "pads", "pas" -> "pals",
"pas" -> "pans", "pas" -> "paps", "pas" -> "pars", "pas" -> "pass",
"pas" -> "past", "pas" -> "pats", "pas" -> "paws", "pas" -> "pays",
"pas" -> "peas", "pas" -> "spas", "pat" -> "pact", "pat" -> "pant",
"pat" -> "part", "pat" -> "past", "pat" -> "pate", "pat" -> "path",
"pat" -> "pats", "pat" -> "peat", "pat" -> "phat", "pat" -> "prat",
"pat" -> "spat", "paw" -> "pawl", "paw" -> "pawn", "paw" -> "paws",
"pay" -> "pacy", "pay" -> "pays", "pay" -> "play", "pay" -> "pray",
"pay" -> "spay", "pea" -> "peak", "pea" -> "peal", "pea" -> "pear",
"pea" -> "peas", "pea" -> "peat", "pea" -> "plea", "spa" -> "spam",
"spa" -> "span", "spa" -> "spar", "spa" -> "spas", "spa" -> "spat",
"spa" -> "spay", "eta" -> "beta", "eta" -> "etas", "eta" -> "feta",
"eta" -> "Leta", "eta" -> "Meta", "eta" -> "zeta", "tab" -> "stab",
"tag" -> "stag", "tag" -> "tags", "tag" -> "tang", "tam" -> "tame",
"tam" -> "tamp", "tam" -> "tams", "tam" -> "team", "tam" -> "tram",
"tan" -> "Stan", "tan" -> "tang", "tan" -> "tank", "tan" -> "tans",
"tan" -> "tarn", "tan" -> "than", "tap" -> "tamp", "tap" -> "tape",
"tap" -> "taps", "tap" -> "tarp", "tap" -> "trap", "tar" -> "star",
"tar" -> "tare", "tar" -> "tarn", "tar" -> "taro", "tar" -> "tarp",
"tar" -> "tars", "tar" -> "tart", "tar" -> "tear", "tat" -> "tact",
"tat" -> "tart", "tat" -> "tats", "tat" -> "taut", "tat" -> "teat",
"tat" -> "that", "tau" -> "taus", "tau" -> "taut", "tax" -> "taxi",
"tea" -> "teak", "tea" -> "teal", "tea" -> "team", "tea" -> "tear",
"tea" -> "teas", "tea" -> "teat", "yak" -> "yaks", "yak" -> "yank",
"yam" -> "yams", "yap" -> "yaps", "yaw" -> "yawl", "yaw" -> "yawn",
"yaw" -> "yaws", "yea" -> "yeah", "yea" -> "year", "yea" -> "yeas"}


UPDATE

Just for fun (and using kguler's beautiful styling) for the "root" "a":

g[u_, n_] := NestList[Join @@ fun /@ Union[#[[All, 2]]] &, fun[u], n];
st[t_, l_] := {GraphLayout -> {"RadialEmbedding", "RootVertex" -> t},
VertexStyle -> {_ :> White, (x_ /; StringLength[x] == l) ->
Directive[{Red, PointSize[.01]}],
t -> Directive[{Blue, PointSize[.01]}]},
VertexLabels -> {Placed["Name",
Tooltip], (x_ /; StringLength[x] == l) ->
Placed[Style[x, Red, 12], {Tooltip, Before}]},
VertexShapeFunction -> "Point", LabelStyle -> Red,
ImageSize -> 700,
EdgeStyle -> Directive[Opacity[.5], Hue[.15, .5, .8]],
Background -> Black, EdgeShapeFunction -> (Line[#1] &)};
With[{bas = g["a", 7]}, Manipulate[
ve = Prepend[
Through[{VertexCount, EdgeCount}[
Graph[Join @@ bas[[1 ;; #]]]]] & /@ Range[8], {1, 0}];
Column[{
Row[{
ListPlot[Transpose[ve], Joined -> True, Frame -> True,
PlotLegends -> {"Vertex Count", "EdgeCount"},
FrameLabel -> {"Base string length", "Count"},
ImageSize -> 250],
ListPlot[Transpose[Differences@(ve)], Joined -> True,
Frame -> True, PlotLegends -> {"Vertex Count", "EdgeCount"},
FrameLabel -> {"Base string length", "Change"},
ImageSize -> 250]}],
grp = Graph[Join @@ bas[[1 ;; s]], st["a", s + 1]]
}],
{s, Range[8]}]]


• Excellent. Yes... a single letter ANYWHERE in the word (including as a prefix or suffix). The graph actually thins out for words of length greater than 5. A clearer way to present the graph is TreePlot[Join @@ gr, Center]. Oct 15 '14 at 17:11

I am the original poser of this question which is not a homework question as belisarius could have realized by noting my identity. (Frankly, belisarius' statement that it was related to a homework problem he assigned did nothing to help me and others interested, and in fact apparently dissuaded others from addressing this problem. I grant that all would have been clearer had I shown my attempts.)

To wit: I addressed this problem with this function:

NewExpander::usage = "NewExpander[x] takes a string x and produces a list of all valid English words formed by inserting a single letter in every possible slot in x, e.g., NewExpander['cat'] = {'cat',{'cant','cart','cast','cats','chat','coat','scat'}}";
NewExpander[x_: String] := {x, Select[
Union@
Flatten@Table[
StringInsert[x, #, ll] & /@ CharacterRange["a", "z"], {ll, 1,
StringLength[StringTake[x, -1]] + 1}],
DictionaryLookup[#] != {} &]} /; Depth[x] == 1


Then I wrote code to convert the output of NewExpander[ ] into the list of links from the source word to each of the descendant words using Outer[ ]:

Flatten[Outer[
Rule, {#[[1]]}, #[[2]]] & /@ {{"a", {"ad", "ah", "am", "an", "as",
"at", "ax", "fa", "ha", "la", "ma", "pa", "ta",
"ya"}}, {"i", {"bi", "hi", "id", "if", "in", "is", "it", "mi",
"oi", "pi", "ti", "xi"}}}, \[Infinity]]


This is useful for creating a list of links to be used by TreeGraph[ ].

The problem was then nesting the NewExpander[ ] code so that it iteratively expanded only the deepest levels in the resulting list and keeping all the nesting levels organized, as needed by the problem.

• Fyi, don't know if it's already been mentioned: en.wikipedia.org/wiki/Trie. Discussed in Brass' book: amazon.com/Advanced-Data-Structures-Peter-Brass/dp/0521880378 Oct 15 '14 at 2:49
• Please consider my comment also the other around: Should you be one of my students it would be quite unfair not telling you that I was looking over your shoulder. That said, I'm sorry if my comment really impaired your chances of getting more/better answers Oct 17 '14 at 18:25