How to draw graphs in LaTeX?

I think the best approach is to use the tkz-berge from Altermundus. You can also find a complete guide here.

However, to make a simple example just using TikZ, you can follow this approach:

\documentclass {article}

% example taken from 
% http://www.guitex.org/home/images/doc/GuideGuIT/introingtikz.pdf

\usepackage {tikz}
\usetikzlibrary {positioning}
%\usepackage {xcolor}
\definecolor {processblue}{cmyk}{0.96,0,0,0}
\begin {document}
\begin {center}
\begin {tikzpicture}[-latex ,auto ,node distance =4 cm and 5cm ,on grid ,
semithick ,
state/.style ={ circle ,top color =white , bottom color = processblue!20 ,
draw,processblue , text=blue , minimum width =1 cm}]
\node[state] (C)
{$1$};
\node[state] (A) [above left=of C] {$0$};
\node[state] (B) [above right =of C] {$2$};
\path (A) edge [loop left] node[left] {$1/4$} (A);
\path (C) edge [bend left =25] node[below =0.15 cm] {$1/2$} (A);
\path (A) edge [bend right = -15] node[below =0.15 cm] {$1/2$} (C);
\path (A) edge [bend left =25] node[above] {$1/4$} (B);
\path (B) edge [bend left =15] node[below =0.15 cm] {$1/2$} (A);
\path (C) edge [bend left =15] node[below =0.15 cm] {$1/2$} (B);
\path (B) edge [bend right = -25] node[below =0.15 cm] {$1/2$} (C);
\end{tikzpicture}
\end{center}
\end{document}

which leads to:

It is an example of a Markov Chain in which several TikZ options are used. In the same guide, you will find an example in which nodes are placed in a matrix.

You can use the tkz-berge package . This package uses TikZ it's possible to add all the commands of TikZ.

Here the three classic forms of Petersen's graph

\documentclass[11pt]{scrartcl}
\usepackage{tkz-berge}


\begin{document}
\begin{tikzpicture}[scale=.5] 
\GraphInit[vstyle=Art] 
\SetGraphArtColor{red}{olive} 
\grPetersen[form=1,RA=5,RB=3]%
\end{tikzpicture}
\begin{tikzpicture}[scale=.4]
   \GraphInit[vstyle=Art] 
   \SetGraphArtColor{red}{olive} 
   \grPetersen[form=2,RA=7,RB=3]%
\end{tikzpicture}

\begin{tikzpicture}[scale=.5]
   \GraphInit[vstyle=Art] 
   \SetGraphArtColor{red}{olive} 
   \grPetersen[form=3,RA=7]%
\end{tikzpicture}
\end{document}

I wrote a document with some classic named graphs. It's inside the your distribution (>2011 I think)

texdoc NamedGraphsin the terminal

I added the sources and all the examples you can also find them here

NamedGraphs

Here an example to draw the Petersen's graph only with TikZ I try to structure correctly the code. The first scope is used for vertices ans the second one for edges. The only problem is to get the edges with `mod``

       \pgfmathtruncatemacro{\nextb}{mod(\i+1,5)}
       \pgfmathtruncatemacro{\nexta}{mod(\i+2,5)} 

The complete code

  \documentclass[border=6pt]{standalone}
  \usepackage{tikz}

  \begin{document}

  \begin{tikzpicture} 
    \begin{scope} [vertex style/.style={draw,
                                       circle,
                                       minimum size=6mm,
                                       inner sep=0pt,
                                       outer sep=0pt,
                                       shade}] 
      \path \foreach \i in {0,...,4}{%
       (72*\i:2) coordinate[vertex style] (a\i)
       (72*\i:4) coordinate[vertex style] (b\i)}
       ; 
    \end{scope}

     \begin{scope} [edge style/.style={draw=gray,double=white}]
       \foreach \i  in {0,...,4}{%
       \pgfmathtruncatemacro{\nextb}{mod(\i+1,5)}
       \pgfmathtruncatemacro{\nexta}{mod(\i+2,5)} 
       \draw[edge style] (a\i)--(b\i);
       \draw[edge style] (a\i)--(a\nexta);
       \draw[edge style] (b\i)--(b\nextb);
       }  
     \end{scope}

  \end{tikzpicture}
  \end{document}