import random
d = {'b': ['bob', 'bun', 'bom'], 'd': ['dob', 'don'], 'm': ['mox']}

print(d)
seq = []
current = 'bob'
seq.append(current)
d[current[:1]].remove(current)
while current[-1:] in d and d[current[-1:]]:
    next_ = random.choice(d[current[-1:]])
    current = next_
    seq.append(current)
    d[current[:1]].remove(current)

print(d)
print(seq)

{'b': ['bob', 'bun', 'bom'], 'd': ['dob', 'don'], 'm': ['mox']}
{'b': ['bun'], 'd': ['dob', 'don'], 'm': []}
['bob', 'bom', 'mox']