Fastest way to find all neighbours of a vertex in a graph
As of Mathematica 9.0 we have the function AdjacencyList[g,v].
Since this is built into Mathematica, I would assume that it is the fastest implementation.

In[1]:= g = CompleteGraph[7];
In[2]:= AdjacencyList[g, 4]
Out[2]= {1, 2, 3, 5, 6, 7}
In[3]:= g = CompleteGraph[{3,4}];
In[4]:= EdgeList[g]
Out[4]= {1 &lt;-&gt; 4, 1 &lt;-&gt; 5, 1 &lt;-&gt; 6, 1 &lt;-&gt; 7, 2 &lt;-&gt; 4, 2 &lt;-&gt; 5, 2 &lt;-&gt; 6, 2 &lt;-&gt; 7, 3 &lt;-&gt; 4, 3 &lt;-&gt; 5, 3 &lt;-&gt; 6, 3 &lt;-&gt; 7}
In[5]:= AdjacencyList[g, 5]
Out[5]= {1, 2, 3}