Megoldás. A feladatnak nyilván csak $n\le k$ esetén van értelme. Ha $n=k$, akkor bármely két szó legalább két helyen különbözik, tehát nincs él a gráfban; ekkor a gráf átmérője végtelen. Legyen a továbbiakban $n<k$.
Megmutatjuk, hogy a gráf átmérője (az érdektelen $n=1$ esettől eltekintve) $\left[\frac{3n}{2}\right]$. Tekintsük először azt az esetet, amikor $n$ páros. Vegyünk egy tetszőleges $A_1{A}_2{A}_3\text{...}{A}_n$ szót. Vizsgáljuk meg, hogy ez milyen távol van az $A_2{A}_1{A}_4{A}_3\text{...}{A}_n{A}_{n-1}$ szótól. Nézzük meg, hány élen kell végigmenni, hogy az $A_1{A}_2$ részből $A_2{A}_1$ legyen. Nevezzük lépésnek azt, amikor egy élen áthaladunk. Mivel különböző betűkből állnak a szavak, kell lennie egy olyan lépésnek, ahol $A_1$ vagy $A_2$ megváltozik egy $A_1$-től és $A_2$-től különböző betűre. Kell még két lépés, amikor az első helyre $A_2$, és amikor a másodikra $A_1$ kerül. Tehát legalább három lépésre van szükség. A különböző helyeken lévő változások egymást nem befolyásolják, ezért $\frac{n}{2}\cdot 3$ lépést kell (legalább) elvégezni ahhoz, hogy $A_1{A}_2{A}_3\text{...}{A}_n$-ből $A_2{A}_1{A}_4{A}_3\text{...}{A}_n{A}_{n-1}$-be érjünk.
Ha $n$ páratlan, akkor az $A_1{A}_2{A}_3\text{...}{A}_n$ és az $A_2{A}_1{A}_4{A}_3\text{...}{A}_{n-1}{A}_{n-2}{A}_{n+1}$ szó távolsága (ahol $A_{n+1}\ne A_1\mathrm{,}{A}_2\mathrm{,}{A}_3\mathrm{,}\text{...}\mathrm{,}{A}_n$) az előző esethez hasonlóan