The vertices that tkz-berge draws are regular named TikZ nodes, and so they can be used if one wants unusual edges.

Update: I added four more lines, to show that one can also use the node names provided by tkz-berge, to apply extra labels.

\begin{tikzpicture}
\usetikzlibrary{decorations.pathmorphing,arrows}
\tikzset{EdgeStyle/.append style = {line width=2pt}}
\grEmptyPath[RA=2]{6}
\draw[line width=3pt] (a0) .. controls (-1,1) and (1,1) .. (a0);
\draw[thick,color=blue] (a1) .. controls (0,0) and (2,2) .. (a1);
\draw (a2) .. controls (0,2) and (8,2) .. (a2);
\draw (a3) node[above right=5pt]{$v_{0}$};
\end{tikzpicture}