The largest 3-regular graph of diameter 3

See this paper

\documentclass{article}
\usepackage{tikz}
\pagestyle{empty}

\begin{document}
\begin{center}
\begin{tikzpicture}[style=thick]
\foreach \x in {18,90,...,306}
{
\draw (\x:4cm) circle (2pt) -- (\x+72:4cm);
\draw (\x:4cm) -- (\x:3cm) circle (2pt);
\draw (\x:3cm) -- (\x+15:2cm) circle (2pt);
\draw (\x:3cm) -- (\x-15:2cm) circle (2pt);
\draw (\x+15:2cm) -- (\x+144-15:2cm);
\draw (\x-15:2cm) -- (\x+144+15:2cm);
}
\end{tikzpicture}
\end{center}
\end{document}

The largest 4-regular graph of diameter 2

See this paper.

\documentclass{article}
\usepackage{tikz}
\pagestyle{empty}

\begin{document}
\begin{center}
\begin{tikzpicture}[style=thick]
\foreach \x in {0,30,...,330}
{
\draw (\x:2cm) circle (2pt) -- (\x+30:2cm);
}
\foreach \x in {0,60,...,300}
{
\draw (\x:2cm) circle (2pt) -- (\x+90:2cm);
}
\foreach \x in {0,30,...,150}
{
\draw (\x:2cm) circle (2pt) -- (\x+180:2cm);
}
\draw (60:0.7cm) circle (2pt) --
(180:0.7cm) circle (2pt) --
(300:0.7cm) circle (2pt) -- (60:0.7cm);
\end{tikzpicture}
\end{center}
\end{document}

The McGee graph

\documentclass{article}
\usepackage{tikz}
\pagestyle{empty}

\begin{document}
\begin{center}
\begin{tikzpicture}[style=thick]
\foreach \x in {0,15,...,345}
{
\draw (\x:3cm) circle (2pt) -- (\x+15:3cm);
}
\foreach \x in {0,45,...,135}
{
\draw (\x:3cm) circle (2pt) -- (\x+180:3cm);
}
\foreach \x in {15,60,...,330}
{
\draw (\x:3cm) circle (2pt) -- (\x+105:3cm);
}
\end{tikzpicture}
\end{center}
\end{document}

The Hoffman-Singleton graph

\documentclass{article}

\pagestyle{empty}
\usepackage{tikz}

\begin{document}

\begin{center}
\begin{tikzpicture}[style=thick,scale=0.5]
\def\pentagon{(18:1cm) circle (4pt) node[above right=-1.75pt]{\tiny $4$} --
(90:1cm) circle (4pt) node[above]{\tiny $0$} --
(162:1cm) circle (4pt) node[above left=-1.75pt]{\tiny $1$} --
(234:1cm) circle (4pt) node[below]{\tiny $2$} --
(306:1cm) circle (4pt) node[below]{\tiny $3$} -- (18:1cm)}
\def\pentagram{(18:1cm) circle (4pt) node[above right=-1.75pt]{\tiny $4$} --
(162:1cm) circle (4pt) node[above left=-1.75pt]{\tiny $1$} --
(306:1cm) circle (4pt) node[below]{\tiny $3$} --
(90:1cm) circle (4pt) node[above]{\tiny $0$} --
(234:1cm) circle (4pt) node[below]{\tiny $2$} -- (18:1cm)}
\draw[yshift=4cm] node{\tiny $P_{0}$} \pentagon;
\draw[xshift=3cm,yshift=4cm] node{\tiny $P_{1}$} \pentagon;
\draw[xshift=6cm,yshift=4cm] node{\tiny $P_{2}$} \pentagon;
\draw[xshift=9cm,yshift=4cm] node{\tiny $P_{3}$} \pentagon;
\draw[xshift=12cm,yshift=4cm] node{\tiny $P_{4}$} \pentagon;
\draw node{\tiny $Q_{0}$} \pentagram;
\draw[xshift=3cm] node{\tiny $Q_{1}$} \pentagram;
\draw[xshift=6cm] node{\tiny $Q_{2}$} \pentagram;
\draw[xshift=9cm] node{\tiny $Q_{3}$} \pentagram;
\draw[xshift=12cm] node{\tiny $Q_{4}$} \pentagram;
\draw (6,-2.5) node%
{Vertex $i$ in $P_{j}$ is joined to vertex $i+jk\!\!\!\!\pmod{5}$ of $Q_{k}$};
\end{tikzpicture}
\end{center}
\end{document}

%%% Local Variables:
%%% mode: latex
%%% TeX-master: t
%%% End:

Tutte's 8-cage

The unique smallest cubic graph of girth 8. Drawn from Algebraic Graph Theory by Godsil and Royle, p.72.

\documentclass{article}
\usepackage{tikz}
\pagestyle{empty}

\begin{document}
\begin{tikzpicture}[style=thick]
\foreach \x in {0,36,...,324}
{
\draw (\x:2cm) circle (2pt) -- (\x+144:2cm);
\draw (\x-10:3cm) circle (2pt) -- (\x+5:4cm);
\draw (\x-10:3cm) circle (2pt) -- (\x+36:2cm);
\draw (\x-10:3cm) circle (2pt) -- (\x+170:3cm);
\draw (\x+5:4cm) circle (2pt) -- (\x+41:4cm);
}
\end{tikzpicture}
\end{document}

A complete bipartite graph

\documentclass{article}
\usepackage{tikz}
\pagestyle{empty}

\begin{document}
\begin{center}
\begin{tikzpicture}[style=thick]
\foreach \x in {0,1,2}
\foreach \y in {0,1,2}
{\draw (\y,0) -- (\x,1);}
\foreach \x in {0,1,2}{
\draw (\x,0) circle (2pt);
\draw (\x,1) circle (2pt);}
\end{tikzpicture}
\end{center}
\end{document}

A cubic tree

If it could be completed to a cubic graph, it would give a cubic Moore graph of diameter 3. I wish I knew how to produce a similar tree, but growing from an edge instead of from a vertex.

\documentclass{article}
\usepackage{tikz}
\thispagestyle{empty}
\begin{document}
\newcommand{\twochildren}{child{node{\null}} child{node{\null}}}

\begin{tikzpicture}[style=thick,scale=0.5]
\tikzstyle{every node}=[circle,inner sep=2pt,draw]
\tikzstyle{level 1}=[sibling distance=20mm]
\tikzstyle{level 2}=[sibling distance=10mm]
\tikzstyle{level 3}=[sibling distance=5mm]
\node{\null}[grow'=right]
child{node{\null}
child{node{\null}\twochildren}
child{node{\null}\twochildren} }
child{node{\null}
child{node{\null}\twochildren}
child{node{\null}\twochildren} }
child{node{\null}
child{node{\null}\twochildren}
child{node{\null}\twochildren} };
\end{tikzpicture}
\end{document}

Petersen graph

The smallest cubic graph of girth 5, drawn using TikZ.

\documentclass{article}
\usepackage{tikz}
\pagestyle{empty}

\begin{document}
\begin{center}
\begin{tikzpicture}[style=thick]
\draw (18:2cm) -- (90:2cm) -- (162:2cm) -- (234:2cm) --
(306:2cm) -- cycle;
\draw (18:1cm) -- (162:1cm) -- (306:1cm) -- (90:1cm) --
(234:1cm) -- cycle;
\foreach \x in {18,90,162,234,306}{
\draw (\x:1cm) -- (\x:2cm);
\draw (\x:2cm) circle (2pt);
\draw (\x:1cm) circle (2pt);
}
\end{tikzpicture}
\end{center}
\end{document}

Heawood graph

The smallest cubic graph of girth 6, or 6-cage, drawn with PS Tricks. This was inspired from the example in The LaTeX Graphics Companion, page 121.

\documentclass{article}
\usepackage{pstricks,pst-node,multido,ifthen,calc}
\pagestyle{empty}

\begin{document}
\begin{center}
\begin{pspicture}(-1,-1.5)(1,1.5)
\psset{unit=1.5cm}
\newcounter{CtA}
\newcounter{Temp}
\newcounter{Tempi}
\SpecialCoor \degrees[14]
\multido{\ia=0+1}{14}{%
\setcounter{CtA}{\ia}%
\addtocounter{CtA}{1}%
\multido{\ib=\value{CtA}+1}{1}{\psline{o-o}(1;\ia)(1;\ib)}
}%
\multido{\ia=0+2}{7}{%
\setcounter{CtA}{\ia}%
\addtocounter{CtA}{5}
\multido{\ib=\value{CtA}+1}{1}{\psline{o-o}(1;\ia)(1;\ib)}
}%
\multido{\i=1+1}{14}{\rput(1;\i){%
\setcounter{Temp}{\i}%
\ifthenelse{\isodd{\value{Temp}}}%
{\setcounter{Tempi}{(\value{Temp}+1)/2}}
{\setcounter{Tempi}{(\value{Temp})/2}}
}%
}
\end{pspicture}
\end{center}
\end{document}

The purposes of this blog are to show pictures of graphs (where by a graph we mean the object studied in Graph Theory) produced by LaTeX, and more precisely by its packages Xy-pic, PS Tricks and TikZ, and to discuss pros and cons of each approach.

I am using the Perl script texttogif to obtain the PNG pictures from a LaTeX source.