\documentclass[psamsfonts]{amsart}
\usepackage{amsmath}
\usepackage{amssymb,amsfonts}
\usepackage{amsthm}
\usepackage[all,dvips,arc,curve,color,frame]{xy} 
\usepackage{mathrsfs}
\input{xy} 
\xyoption{all}
\title{Regular Graphs of Given Girth}
\author{Brooke Ullery}
\date{August 3, 2007}

\begin{document}

\maketitle
\tableofcontents

\newtheorem{thm}{Theorem}[section]
\newtheorem{lem}[thm]{Lemma}
\newtheorem{obs}[thm]{Observation}
\newtheorem{exa}[thm]{Example}

\theoremstyle{definition}
\newtheorem{defi}[thm]{Definition}


\section{Introduction}
This paper gives an introduction to the area of graph theory dealing with properties of regular graphs of given girth.  A large portion of the paper is based on exercises and questions proposed by L$\acute{a}$szl$\acute{o}$ Babai in his lectures and in his Discrete Math lecture notes.


\section{Graphs}

Graph theory is the study of mathematical structures called graphs.  We define a \textbf{graph} as a pair $(V,E)$, where $V$ is a nonempty set, and $E$ is a set of unordered pairs of elements of $V$.  $V$ is called the set of \textbf{vertices} of $G$, and $E$ is the set of \textbf{edges}.  Two vertices $a$ and $b$ are \textbf{adjacent} provided $(a,b) \in E$.  If a pair of vertices is adjacent, the vertices are referred to as \textbf{neighbors}.  We can represent a graph by representing the vertices as points and the edges as line segments connecting two vertices, where vertices $a,b \in V$ are connected by a line segment if and only if $(a,b) \in E$.  Figure 1 is an example of a graph with vertices $V=\{x,y,z,w\}$ and edges $E=\{(x,w),(z,w),(y,z)\}$.

\begin{displaymath}
 \xygraph{ 
!{<0cm,0cm>;<2cm,0cm>:<0cm,2cm>::} 
!{(0,0) }*+{\bullet_{z}}="z" 
!{(1,1) }*+{\bullet_{y}}="y"
!{(1,0) }*+{\bullet_{w}}="w"
!{(0,1)}*+{\bullet_{x}}="x"
"x"-"w"
"y"-"z"
"z"-"w"}
\end{displaymath}
\begin{center}
Figure 1
\end{center}


Now we define some relevant properties of graphs.

\begin{defi}
A \textbf{walk} of length $k$ is a sequence of vertices $v_0,v_1,\dots ,v_k$, such that for all $i>0, v_i$ is adjacent to $v_{i-1}$.
\end{defi}

\begin{defi}
A \textbf{connected graph} is a graph such that for each pair of vertices $v_1$ and $v_2$ there exists a walk beginning at $v_1$ and ending at $v_2$.
\end{defi}

\begin{exa}
The graph in Figure 2 is not connected because there is no walk beginning at $z$ and ending at $w$.
\end{exa}

\begin{displaymath}
 \xygraph{ 
!{<0cm,0cm>;<2cm,0cm>:<0cm,2cm>::} 
!{(0,0) }*+{\bullet_{z}}="z" 
!{(1,1) }*+{\bullet_{y}}="y"
!{(1,0) }*+{\bullet_{w}}="w"
!{(0,1)}*+{\bullet_{x}}="x"
"x"-"w"
"y"-"z"}
\end{displaymath}
\begin{center}
Figure 2
\end{center}

From this point on, we will assume that every graph discussed is connected.

\begin{defi}
A \textbf{cycle} of length $k>2$ is a walk such that each vertex is unique except that $v_0=v_k$.
\end{defi}

\begin{defi}
A \textbf{tree} is a graph with no cycles.
\end{defi}

\begin{defi}
The \textbf{girth} of a graph is the length of its shortest cycle.  
\end{defi}

Since a tree has no cycles, we define its girth as $\inf \emptyset = \infty$
\begin{exa}
The graph in figure 3 has girth 3.
\end {exa}

\begin{displaymath}
 \xygraph{ 
!{<0cm,0cm>;<2cm,0cm>:<0cm,2cm>::} 
!{(0,1) }*+{\bullet_{a}}="a" 
!{(1,1) }*+{\bullet_{b}}="b"
!{(0,0) }*+{\bullet_{c}}="c"
!{(1,0)}*+{\bullet_{d}}="d"
!{(1.5,.5)}*+{\bullet_{e}}="e"
"a"-"b"
"a"-"c"
"c"-"d"
"b"-"d"
"d"-"e"
"b"-"e"}
\end{displaymath}
\begin{center}
Figure 3
\end{center}

\begin{defi}
The \textbf{degree} of a vertex is the number of vertices adjacent to it.
\end{defi}

\begin{defi}
A graph is $r$-\textbf{regular} if every vertex has degree $r$.
\end{defi}

\begin{defi}
A \textbf{complete graph} is a graph such that every pair of vertices is connected by an edge.
\end{defi}
We observe that a complete graph with $n$ vertices is $n-1$-regular, and has $${n \choose 2} =\frac{n(n-1)}{2}$$ edges.

\begin{defi}
A \textbf{complete bipartite graph} is a graph whose vertices can be divided into two disjoint sets $X$ and $Y$, such that every vertex in $X$ is adjacent to every vertex in $Y$ and no pair of vertices within the same set is adjacent.
\end{defi}
The complete bipartite graph with $\mid X\mid=x$ and $\mid Y\mid=y$ is denoted $K_{x,y}$.

\begin{defi}
The complement of a graph $G$, denoted $\bar{G}$, is a graph on the same vertices as $G$, only the vertices adjacent in $G$ are not adjacent in $\bar{G}$ and the vertices not adjacent in $G$ are adjacent in $\bar{G}$.
\end{defi}

\begin{exa} 
In Figure 4, $\bar{G}$ is the complement of $G$.
\end{exa}

\begin{displaymath}
 \xygraph{ 
!{<0cm,0cm>;<1.25cm,0cm>:<0cm,1.25cm>::} 
!{(0,1) }*+{\bullet_{a}}="a" 
!{(1,2) }*+{\bullet_{b}}="b"
!{(3,2) }*+{\bullet_{c}}="c"
!{(4,1) }*+{\bullet_{d}}="d"
!{(3,0) }*+{\bullet_{e}}="e" 
!{(1,0) }*+{\bullet_{f}}="f"
!{(5,1) }*+{\bullet_{a}}="aa"
!{(6,2) }*+{\bullet_{b}}="bb"
!{(8,2) }*+{\bullet_{c}}="cc" 
!{(9,1) }*+{\bullet_{d}}="dd"
!{(8,0) }*+{\bullet_{e}}="ee"
!{(6,0) }*+{\bullet_{f}}="ff"
!{(2,2.5) }*+{G}="q"
!{(7,2.5) }*+{\bar{G}}="r"
"a"-"b"
"b"-"c"
"c"-"d"
"d"-"e"
"e"-"f"
"f"-"a"
"b"-"f"
"b"-"e"
"c"-"e"
"c"-"f"
"aa"-"dd"
"aa"-"cc"
"aa"-"ee"
"bb"-"dd"
"ff"-"dd"}
\end{displaymath}
\begin{center}
Figure 4
\end{center}

\vspace{5mm}
\section{Girths of Regular Graphs}
Using only the definitions of the previous section and some elementary linear algebra, we are able to prove some interesting results concerning $r$-regular graphs of a given girth.  We begin with two lemmas upon which the rest of the paper will depend.

\begin{lem}
The number of vertices of an $r$-regular graph with an odd girth of $g=2d+1$ (where $d \in \mathbb{Z}^+$) is $n$, such that
\begin{displaymath}
n\geq 1+\sum_{i=0}^{d-1} r(r-1)^i.
\end{displaymath}
\end{lem}

We will first show this for $g=5$: 
\begin{proof}[Proof of Lemma 3.1 for $g=5$]
Let $G$ be an $r$-regular graph with girth $5$.  Take a vertex $v_0$ of $G$.  Let $V_0=\{ v_0 \}$.  $v_0$ must be adjacent to $r$ vertices.  Let $V_1$ be the set containing those $r$ vertices.  None of the elements of $V_1$ can be adjacent to one another, because that would create a 3-cycle.  Thus, each of those vertices must be adjacent to an additional $r-1$ vertices.  Each of these vertices must be unique in order to avoid creating a 4-cycle.  Let $V_2$ be the set of all vertices adjacent to elements of $V_1$ except $v_0$.  Elements of $V_2$ can be adjacent to one another, creating 5-cycles.  Thus, adding up the vertices in Figure 5, we have 
\begin{eqnarray*}
&& n=1+r+r(r-1) \\
\Rightarrow && n=1+\sum_{i=0}^{1} r(r-1)^i.
\end{eqnarray*}
\end{proof}


\begin{displaymath}
 \xygraph{ 
!{<0cm,0cm>;<1cm,0cm>:<0cm,.5cm>::} 
!{(3,4) }*+{\bullet_{v_0}}="v0" 
!{(1,2) }*+{\bullet}="a"
!{(5,2) }*+{\bullet}="b"
!{(0,0)}*+{\bullet}="c"
!{(2,0)}*+{\bullet}="d"
!{(4,0)}*+{\bullet}="e"
!{(6,0)}*+{\bullet}="f"
!{(3,2)}*+{\cdots \cdots}
!{(1,0)}*+{\cdots}
!{(3,0)}*+{\cdots}
!{(5,0)}*+{\cdots}
!{(8,4)}*+{\textrm{$V_0$ (1 vertex)}}
!{(8,2)}*+{\textrm{$V_1$ ($r$ vertices)}}
!{(8.5,0)}*+{\textrm{$V_2$ ($r(r-1)$ vertices)}}
"v0"-"a"
"v0"-"b"
"a"-"c"
"a"-"d"
"b"-"e"
"b"-"f"}
\end{displaymath}
\begin{center}
Figure 5
\end{center}

\vspace{5mm}

Now we extend this to any $g=2d+1$.

\begin{proof}[Proof of Lemma 3.1]
Let $G$ be an $r$-regular graph with girth $g=2d+1$.  Take a vertex $v_0$ of $G$.  Let $V_0=\{ v_0 \}$.  $v_0$ must be adjacent to $r$ vertices.  Let $V_1$ be the set consisting of those $r$ vertices. None of the elements of $V_1$ can be adjacent to one another without creating a 3-cycle.  Now, we will create more sets of vertices, as in Figure 5. The vertices adjacent to those in $V_1$ (not including $v_0$) will be in the set $V_2$.  Similarly, if $v$ is a vertex, we define $V_k=\{v \mid v$ is adjacent to an element of $V_{k-1}$ and $v \notin V_n$ where $n<k-1 \}$ .  There can be no cycles within vertices in  $\bigcup_{i=0}^{d-1} V_i$.  Suppose there were such a cycle.  Then, without loss of generality, we can assume that the cycle is a result of an adjacency between two elements within the same set $V_n$.  Then, there would be a $2n+1$-cycle, and since $n<d$, $2n+1$ must be less than $g$.  Thus, there can be no such cycle, which implies that each vertex of $V_d$ is a unique vertex of $G$. Each set $V_n$ ($<n\leq d$) has a cardinality of $(r-1)$ times the number of vertices of $V_{n-1}$, and $V_1$ has $r$ vertices.  Thus, $V_k$ has $r(r-1)^{k-1}$ vertices.  So, summing the cardinalities of $V_0$ through $V_d$ we have, 
$$n\geq 1+\sum_{i=0}^{d-1} r(r-1)^i$$ 
\end{proof}

We now give a similar lemma for graphs of even girth.

\begin{lem}
The number of vertices of an $r$-regular graph with a girth of $g=2d$ (where $d \geq 2$) is $n$, where
$$n \geq 1+(r-1)^{d-1}+\sum_{i=0}^{d-2} r(r-1)^i=2\sum_{i=0}^{d-1}(r-1)^i.$$
\end{lem}

We will prove this in two different ways.  In the first proof, we will begin with a vertex of the graph, as in the proof of Lemma 3.1, and in the second one we will begin with two adjacent vertices.

\begin{proof}[Proof \#1 of Lemma 3.2]
Let $G$ be an $r$-regular graph with girth $g=2d$, where $d \geq 2$.  Let $v_0$ be a vertex in $G$.  Let $V_0=\{ v_0 \}$.  $v_0$ must be adjacent to $r$ vertices.  Let $V_1$ be the set consisting of those $r$ vertices. None of the elements of $V_1$ can be adjacent to one another without creating a 3-cycle. The vertices adjacent to those in $V_1$ (not including $v_0$) will be in the set $V_2$.  Similarly, if $v$ is a vertex, we define $V_k=\{v \mid v$ is adjacent to an element of $V_{k-1}$ and $v \notin V_n$ where $n<k-1 \}$ .  There can be no cycles within vertices in  $\bigcup_{i=0}^{d-1} V_i$.  Suppose there were such a cycle.  Then, without loss of generality, we can assume that the cycle is a result of an adjacency between two elements within the same set $V_n$.  Then, there would be a $2n+1$-cycle, and since $n<d$, $2n+1$ must be less than $g$.  Thus, there can be no such cycle, which implies that there must be more vertices than just those in sets $V_1$ through $V_{d-1}$.  Each set $V_n$ ($n>0$) has a cardinality of $(r-1)$ times the number of vertices of $V_{n-1}$, and $V_1$ has $r$ vertices.  Thus, $V_k$ has $r(r-1)^{k-1}$ vertices.  Thus, we have counted a total of
$$n\geq 1+\sum_{i=0}^{d-2} r(r-1)^i$$
vertices so far.  However, each vertex in $V_{d-1}$ must have $r-1$ additional neighbors which are not in $\bigcup_{i=0}^{d-1}V_i$ in order to satisfy the girth requirement of $2d$ and $r$-regularity.  That gives $r(r-1)^{d-1}$ additional vertices.  However, these vertices need not be unique in order to create a $2d$-cycle.  Since each of the vertices can have at most $r$ neighbors within $V_{d-1}$, we can divide by $r$ so that we only actually need an additional  $(r-1)^{d-1}$ unique vertices.  So, summing the cardinalities of $V_0$ through $V_{d-1}$, and the additional vertices that are adjacent to those in $V_{d-1}$, we have, 
$$n \geq 1+(r-1)^{d-1}+\sum_{i=0}^{d-2} r(r-1)^i.$$
\end{proof}

\begin{proof}[Proof \#2 of Lemma 3.2]
Let $G$ be an $r$-regular graph with girth $g=2d$, where $d \geq 2$.  Let $a_0$ and $b_0$ be adjacent vertices in $G$.  Let $V_1=\{a_0,b_0\}$.  Each vertex in $V_1$ must be adjacent to an additional $r-1$-vertices.  These vertices must be unique in order to prevent a 3-cycle from being created.  Define $V_2$ as the set of the $2(r-1)$ vertices adjacent to the vertices in $V_1$ (not including elements of $V_1$.  Similar to the first proof, we define $V_k=\{v \mid v$ is adjacent to an element of $V_{k-1}$ and $v \notin V_n$ where $n \leq k-1 \}$.  There can be no cycles within vertices in  $\bigcup_{i=0}^{d-1} V_i$.  Suppose there were such a cycle.  Then, without loss of generality, we can assume that the cycle is a result of an adjacency between two elements within the same set $V_n$.  Then, there would be a $2n$-cycle, and since $n<d$, $2n$ must be less than $g=2d$. Thus, there can be no such cycle, which implies (since $g$ is even) that each vertex of $V_d$ is a unique vertex of $G$.  Each set $V_n$ has a cardinality of $(r-1)$ times the number of vertices of $V_{n-1}$ and $V_1$ has 2 vertices.  Thus, $V_k$ has $2(r-1)^{k-1}$ vertices.  So, summing the cardinalities of $V_1$ through $V_d$, we obtain
$$n \geq 2\sum_{i=0}^{d-1}(r-1)^i.$$

Now, simple algebra shows that $1+(r-1)^{d-1}+\sum_{i=0}^{d-2} r(r-1)^i=2\sum_{i=0}^{d-1}(r-1)^i:$
Let $x=r-1$.  Then the left hand side of the equation becomes:
\begin{eqnarray*}
 LHS&=&(x+1) \sum_{i=0}^{d-2}x^i+x^{d-1}+1 \\
 &=& \frac{(x+1)(x^{d-1}-1)}{x-1}+x^{d-1}+1\\
 &=&\frac{1}{x-1} \left[ (x+1)(x^{d-1}-1)+(x^{d-1}+1)(x-1)\right] \\
 &=& \frac{1}{x-1}(x^d-x+x^{d-1}-1+x^d-x^{d-1}+x-1)\\
 &=& \frac{2x^d-2}{x-1}=2\left(\frac{x^d-1}{x-1}\right)=2\sum_{i=0}^{d-1}x^i=2\sum_{i=0}^{d-1}(r-1)^i=RHS
\end{eqnarray*}
\end{proof}

\section{Minimal Regular Graphs of Given Girth}
A natural question that arises from the lemmas in the previous section is when do the equalities hold?  That is, for which pairs of $g=2d+1$ and $r$ can we find a graph such that the number of vertices is 
\begin{equation}
n=1+\sum_{i=0}^{d-1} r(r-1)^i,
\end{equation}
and for which pairs of $g=2d$ and $r$ can we find a graph such that the number of vertices is
\begin{equation}
n =2\sum_{i=0}^{d-1}(r-1)^i?
\end{equation}
  For small values of $g$ there are many values of $r$ for which the equality holds.  We begin with $g=3$.  In this case, we must find $r$-regular graphs with girth 3 and $1+r(r-1)^0=1+r$ vertices.


\begin{obs}
For every integer $r>1$, there exists an $r$-regular graph with girth $3$ and exactly $r+1$ vertices.
\end{obs}

\begin{proof}
Given an integer $r>1$, the complete graph with $r+1$ vertices is $r$-regular and has a girth of 3.
\end{proof}

In order to further understand regular graphs of given girth, we must introduce some linear algebra relevant to graph theory.

\begin{defi}
The \textbf{adjacency matrix} $A$ of a graph $G$ is the square matrix whose entries are $a_{ij}$, where
\begin{displaymath}
a_{ij} = \left\{ \begin{array}{ll} 
1 & \textrm{if $i$ and $j$ are adjacent}\\ 
0 & \textrm{otherwise.}
\end{array} \right.
\end{displaymath}
\end{defi}

Clearly, the adjacency matrix of a (non-directed) graph is symmetric, that is $A^T=A$, since adjacency is a symmetric relation.  That is, $i$ is adjacent to $j \Longleftrightarrow j$ is adjacent to $i$.  We also observe that the sum of the entries of the $i$th row or of the $i$th column is equal to the degree of the $i$th vertex.  Therefore, the sum of any row or any column of the adjacency matrix of an $r$-regular graph is $r$.

A result of the spectral theorem is that every symmetric matrix has an orthonormal eigenbasis, and real eigenvalues.  Thus, the same holds for every adjacency matrix.

\begin{obs}
The square of an adjacency matrix has entries $b_{ij}$, where $b_{ij}$ is equal to the number of vertices which are adjacent to both vertex $i$ and vertex $j$ for $i\neq j$, and $b_{ii}$ is equal to the degree of vertex $i$.
\end{obs}

\begin{proof}
Suppose $A$ is an $n$ by $n$ adjacency matrix of a labeled graph.  Then, by matrix multiplication, $A^2$ will have entries $b_{ij}$, where $$b_{ij}=\sum_{k=1}^{n} a_{ik}a_{kj}.$$  We notice that the product $a_{ik}a_{kj}$ will be nonzero if and only if $k$ is adjacent to both $i$ and $j$, in which case $a_{ik}=1$ and $a_{kj}=1$ so $a_{ik}a_{kj}=1$.  Thus, $$b_{ij}=\sum_{k=1}^{l} 1=l,$$ where $l$ is the number of vertices which are adjacent to both vertex $i$ and vertex $j$.  $b_{ii}$ will thus simply be the number of vertices adjacent to $i$, or the degree of $i$, since $i$ shares all adjacencies with itself.
\end{proof}

Since each entry of $A^2$ has a geometric interpretation within the graph, it is reasonable to infer that the same holds for $A^k$.  In fact, we can state the following lemma.

\begin{obs}
Let $A$ be an adjacency matrix of a labeled graph $G$, with $n$ vertices.  Then the entry $a_{ij}$ of $A^k$, where $k \geq 1$, is the number of walks of length $k$ from vertex $j$ to vertex $i$. 
\end{obs}

\begin{proof}[Proof by Induction]
The statement holds for $k=1$ by the definition of an adjacency matrix.  Assume the statement holds for $k=l$.  Then, we multiply $A^l$ and $A$ to obtain $A^{l+1}$.  It does not matter in which order we multiply them since matrix multiplication is associative.  Let the entries of $A$ be denoted $b_{ij}$ and let the entries of $A^l$ be denoted $c_{ij}$.  The entry $a_{ij}$ of $A^{l+1}$ is the dot product of the $i$th row of $A$ and the $j$th column of $A^l$.  That is, 
$$a_{ij}=\sum_{m=1}^n b_{im}c_{mj}.$$
We notice that the product $b_{im}c_{mj}$ will be nonzero if and only if $i$ is adjacent to $m$ and there is at least one walk of length $l$ from $j$ to $m$.  this is equivalent to saying there is at least one walk of length $l+1$ from $j$ to $i$ whose second to last vertex is $m$.  Thus, if $b_{im}c_{mj}$ is nonzero, it is equal to the number of walks of length $l+1$ from $j$ to $i$ whose second to last vertex is $m$.  Thus, summing over $n$, we find that $a_{ij}=\sum_{m=1}^n b_{im}c_{mj}$ is the total number of walks of length $l$ from $j$ to $i$.
\end{proof}

Now that we have studied adjacency matrices, let us briefly return to $r$-regular graphs of girth 3 with $r+1$ vertices (complete graphs) in order to give an example.  

\begin{exa}
Let $G$ be a complete graph of degree $r>1$, and let $A$ be its adjacency matrix.  Since $G$ is complete, the entries of $A$ are
\begin{displaymath}
a_{ij} = \left\{ \begin{array}{ll} 
0 & \textrm{if $i = j$}\\ 
1 & \textrm{if $i\neq j$.}
\end{array} \right.
\end{displaymath}
Also, since $G$ has $r+1$ vertices, every pair of unique vertices has exactly $r-1$ neighbors in common, so the entries of $A^2$ are
\begin{displaymath}
a_{ij} = \left\{ \begin{array}{ll} 
r & \textrm{if $i=j$}\\ 
r-1 & \textrm{if $i \neq j$.}
\end{array} \right.
\end{displaymath}
Thus, for the adjacency matrix of the complete graph, the following equality holds:
$$A+A^2=rJ,$$
where $J$ is the matrix of all ones.
\end{exa}

Now, let us look at $r$-regular graphs of girth $g=4$ ($d=2$).  According to Lemma 3.2, at least $n$ vertices are required to make such a graph, where 
$$2\sum_{i=0}^1(r-1)^i=2(r-1)^0+2(r-1)^1=2+2r-2=2r.$$
In fact, only $2r$ vertices are \textit{required}, as stated in the following lemma.

\begin{lem}
For every integer $r>1$, the only $r$-regular graph $G$ that has girth $g=4$ and exactly $2r$ vertices is the complete bipartite graph $K_{r,r}$.
\end{lem}

\begin{proof}
Let $x$ be a vertex in $G$.  $x$ is adjacent to $r$ vertices.  Let $Y$ be the set of vertices adjacent to $x$.  Let $X$ be the set of $r$ vertices not adjacent to $x$ (including $x$ itself).  No two vertices in $Y$ can be adjacent without creating a 3-cycle.  Thus, every vertex of $Y$ must be adjacent to every vertex in $X$ in order for $G$ to be $r$-regular.   Thus, no two vertices in $X$ can be adjacent without creating a $3$-cycle.  Therefore, $G$ is the complete bipartite graph $K_{r,r}$.  Suppose $v \in X$ and $z \in Y$.  Then, the vertices $x$, $y$, $v$, and $z$ create a four cycle.  Thus, $G$ has girth 4.
\end{proof}


By using Lemma 4.6, we can make the following observation about the adjacency matrix of an $r$-regular graph of girth four with $2r$ vertices:

\begin{obs}
Let $G$ be an $r$-regular graph of girth four with $2r$ vertices, and let $A$ be an adjacency matrix of $G$.  Then the following equality holds:
$$A^2+rA=rJ.$$
\end{obs}

\begin{proof}
Let $i$ and $j$ be vertices in $G$.  Since $G$ is a complete bipartite graph, $i$ and $j$ have $r$ neighbors in common if $i$ is not adjacent to $j$ and no neighbors in common if $i$ is adjacent to $j$.  Thus, $A^2$ has zeros where $A$ has ones, and $r$'s where $A$ has zeros.  Thus,
$$A^2+rA=rJ.$$
\end{proof}

Now let us approach the problem of when the equality in equation (1) holds for regular graphs of girth $g=5$ ($d=2$).  That is, we must find for which values of $r$ we can find a graph with girth 5 and $n$ vertices, where
$$n=1+r(r-1)^0+r(r-1)^1=1+r+r^2-r=1+r^2$$
It turns out that there are only a finite number of values of $r$ for which the equality holds.  In fact, there are at most 5 values: \{1,2,3,7,57\}.  We say "at most" because such a graph has not yet been discovered for $r=57$.  To give an idea of how complex the graphs become as $r$ increases, let's look at the simplest of these graphs:

\begin{displaymath}
 \xygraph{ 
!{<0cm,0cm>;<2cm,0cm>:<0cm,2cm>::} 
!{(0,0) }*+{\bullet_{a}}="a" 
!{(1,0) }*+{\bullet_{b}}="b"
"a"-"b"}
\end{displaymath}
\begin{center}
Figure 6: $r=1$, $n=2$
\end{center}

\begin{displaymath}
 \xygraph{ 
!{<0cm,0cm>;<1.5cm,0cm>:<0cm,1.5cm>::} 
!{(.81,1.54) }*+{\bullet_{a}}="a" 
!{(1.62,.95) }*+{\bullet_{b}}="b"
!{(1.31,0) }*+{\bullet_{c}}="c"
!{(.31,0)}*+{\bullet_{d}}="d"
!{(0,.95)}*+{\bullet_{e}}="e"
"a"-"b"
"b"-"c"
"c"-"d"
"d"-"e"
"a"-"e"}
\end{displaymath}
\begin{center}
Figure 7: $r=2$, $n=5$
\end{center}

\begin{displaymath}
 \xygraph{ 
!{<0cm,0cm>;<3cm,0cm>:<0cm,3cm>::} 
!{(.81,1.54) }*+{\bullet_{a}}="a" 
!{(1.62,.95) }*+{\bullet_{b}}="b"
!{(1.31,0) }*+{\bullet_{c}}="c"
!{(.31,0)}*+{\bullet_{d}}="d"
!{(0,.95)}*+{\bullet_{e}}="e"
!{(.81,1.115)}*+{\bullet_{f}}="f"
!{(1.215,.82)}*+{\bullet_{g}}="g"
!{(1.06,.345)}*+{\bullet_{h}}="h"
!{(.56,.345)}*+{\bullet_{i}}="i"
!{(.405,.82)}*+{\bullet_{j}}="j"
"a"-"b"
"b"-"c"
"c"-"d"
"d"-"e"
"a"-"e"
"f"-"h"
"h"-"j"
"j"-"g"
"g"-"i"
"i"-"f"
"a"-"f"
"b"-"g"
"c"-"h"
"d"-"i"
"j"-"e"}
\end{displaymath}
\begin{center}
Figure 8 (Petersen Graph): $r=3$, $n=10$
\end{center}

\vspace{5mm}
The graph for $r=7$ is called the Hoffman-Singleton graph, and has 50 vertices and 175 edges.  In fact, the theorem in this section regarding graphs of girth five is known as the Hoffman-Singleton Theorem.  Before we state the Hoffman-Singleton Theorem, we must discuss some features of regular graphs with girth $\geq$ 5 for which the equality in equation (1) holds.

\begin{lem} If $G$ is an $r$-regular graph, has girth at least 5, and $n = r^2+1$ vertices, the 
number of common neighbors of a pair x, y of vertices is zero if x, y are adjacent and 1 if x, y 
are not adjacent.
\end{lem}

\begin{proof}
For this proof, we will be directly referring to the proof of Lemma 3.1 for $g=5$ and to Figure 5.  Without loss of generality, let $x=v_0$.

\textit{Case 1:} $y \in V_1$.  In this case, $y$ is adjacent to $x$ and $x$ and $y$ have no neighbors in common, so the lemma holds.

\textit{Case 2:} $y \in V_2$.  In this case, $y$ is not adjacent to $x$, and $x$ and $y$ are both adjacent to exactly one vertex in $V_1$.  Thus the lemma holds.
\end{proof}


\begin{thm}[Hoffman-Singleton Theorem] If there exists an $r$-regular graph $G$ of girth greater than or equal to 5 such that the number of vertices $n$ satisfies the equality $n=r^2+1$, then $r\in \{1,2,3,7,57\}$.
\end{thm}

See appendix for proof.

\section{Further Studies}
It is possible to study the minimal regular graphs of girth greater than $5$, however, such studies require more complex mathematical tools than those used in this paper, and some have even been studied with no success yet.

\newpage
\section{Appendix}
The following proof was given in a lecture by L$\acute{a}$szl$\acute{o}$ Babai.  I added it for completeness of the paper.

\begin{proof}[Proof of Theorem 4.9]
Let $A$ be the adjacency matrix of $G$, and let $\bar{A}$ be the adjacency matrix of $\bar{G}$.  By Observation 4.3 and Lemma 4.8, we have 
\begin{equation}
A^2=\bar{A}+rI,
\end{equation}
where $I$ is the identity matrix.
Also, by the definition of the complement of  a graph, we have
\begin{equation}
A+\bar{A}+I=J,
\end{equation}
where $J$ is the matrix of all ones.  Thus, substituting equation (3) into equation (4), we have
\begin{eqnarray}
 &&A+(A^2-rI)+I=J \nonumber \\
 \Rightarrow && A+A^2-(r-1)I=J
\end{eqnarray}

As observed earlier, the sum of the elements of each row of $A$ is $r$.  Thus,
$$A \cdot \textbf{1} = \left[\begin{array}{c}r \\r \\ \vdots \end{array}\right], $$
where \textbf{1} is the vector of all ones.  So we have $A \cdot \textbf{1} = r \cdot \textbf{1}$, which implies that \textbf{1} is an eigenvector of $A$ with eigenvalue $r$.  By the Spectral Theorem (as described earlier), $A$ has an orthogonal eigenbasis, $ \textbf{e}_1 = \textbf{1}, \textbf{e}_2, \ldots, \textbf{e}_n$.  That is, $\textbf{e}_i \perp \textbf{e}_j$ for all pairs of $i,j \in \{1,2, \ldots ,n\}$ such that $i \neq j$.  Thus, $ \textbf{1} \perp \textbf{e}_i$ for all $i \geq 2$.  So, for $i \geq 2$, we have
$$J \textbf{e}_i = \left[\begin{array}{c} \textbf{e}_i \cdot \textbf{1} \\ \vdots \\ \textbf{e}_i \cdot \textbf{1} \end{array}\right]=\textbf{0}.$$

Multiplying equation (5) by $\textbf{e}_i$ ($i \geq 2$) to the right, we obtain
\begin{equation}
(A^2 + A - (r-1) I) \textbf{e}_i = J\textbf{e}_i = \textbf{0}.
\end{equation}
We know that $A\textbf{e}_i = \lambda_i \textbf{e}_i$, and thus $A^2 \textbf{e}_i = \lambda_i^2 \textbf{e}_i$, so equation (6) becomes
$$\lambda_i \textbf{e}_i +\lambda_i \textbf{e}_i - (r-1)\textbf{e}_i=\textbf{0},$$
and thus
\begin{equation}
\lambda_i^2+\lambda_i-(r-1)=0.
\end{equation}
Since this is a quadratic equation, we know that it has at most 2 roots. Thus, $A$ must have at most 3 eigenvalues; let's call them $r$, $\mu_1$, and $\mu_2$ with multiplicities 1, $m_1$, and $m_2$ respectively.

$\mu_1$ and $\mu_2$ must be roots of equation (7).  Thus, we have
$$\mu_{1,2}=\frac{-1\pm \sqrt{1+4(r-1)}}{2}=\frac{-1\pm \sqrt{4r-3}}{2}.$$
Let $s=\sqrt{4r-3}$.  Then, $s^2=4r-3$, or , equivalently,
\begin{equation}
r=\frac{s^2+3}{4}.
\end{equation}

Since $A$ is an $n$ by $n$ matrix, we have
\begin{equation}
1+m_1+m_2=n.
\end{equation}
We also know that the sum of the eigenvalues is equal to the trace of the matrix, so
\begin{equation}
r+m_1 \mu_1 +m_2 \mu_2 = 0.
\end{equation}
Since $n=r^2+1$, we can rewrite equation (9) as
\begin{equation}
m_1+m_2=r^2.
\end{equation}

We know that 
$$\mu_{1,2}=\frac{-1 \pm s}{2}.$$
Without loss of generality, let
$$\mu_1=\frac{-1 + s}{2} \hspace{4mm} \textrm{and} \hspace{4mm} \mu_2=\frac{-1 - s}{2}.$$
Now we can rewrite equation (10) as
$$r+m_1 \frac{-1+s}{2} + m_2 \frac{-1-s}{2} = 0,$$
or
\begin{equation}
2r+s(m_1-m_2)-(m_1+m_2)=0.
\end{equation}

Consider the case where $s$ is irrational.  Then $m_1-m_2=0$ (since $m_1$, $m_2$, and $r$ are all integers), and we have
$$2r-(m_1+m_2)=0,$$
or
$$2r-r^2=0,$$
by equation (11).  Since $r\neq 0$, this equation implies that $r=2$.  This number does, in fact, occur in the theorem as a possible value of $r$.

From now on, we will assume that $s$ is rational, and thus $s$ is an integer (since it is the square root of an integer).

Substituting equation (11) into equation (12), we have
$$2r+s(m_1-m_2)-r^2=0.$$
Plugging in equation (8), we have
$$2\frac{s^2+3}{4}+s(m_1-m_2)-\frac{(s^2+3)^2}{16}=0.$$
Simplifying, we obtain
$$s^4-2s^2-16(m_1-m_2)s-15=0.$$
Thus, $s$ must be a divisor of 15.  That is, $s\in\{\pm1,\pm3,\pm5,\pm15\}$.  Thus, by equation (7), we have $r\in\{1,3,7,57\}$.  Including the case where $s$ is irrational, we add 2 to the possible values of $r$, which brings us to the conclusion that $r\in\{1,2,3,7,57\}$.

\end{proof}


\begin{thebibliography}{100}
 
\bibitem{Babai} Babai, L$\acute{a}$szl$\acute{o}$.  Lectures and \textit{Discrete Math Lecture Notes}.
 
\bibitem{Biggs}  Biggs, Norman. \textit{Algebraic Graph Theory}. 2nd ed. Cambridge: Cambridge UP, 1993.
 
\end{thebibliography} 




\end{document}