BFS for transforming one word to another
The maximum degree of a vertex is $25n$, since this is the number of words which can be obtained by changing a single character. I'm not sure how you get to $26^n$.

You are writing "$4$ is more than $O(n)$" (where $n=2$). This is completely meaningless, since $O(n)$ stands for a function bounded by $Cn$ for some unknown constant $C$. If you don't know the value of $C$ (in this case, $C=25$) then you cannot possibly determine that $4 &gt; Cn$.