\documentclass[12pt]{article}
\usepackage{e-jc}
\specs{}{}{}

\usepackage{amsmath,amsthm,amssymb}
\makeatletter
\renewcommand{\pod}[1]{\allowbreak\mathchoice
  {\if@display \mkern 18mu\else \mkern 8mu\fi (#1)}
  {\if@display \mkern 18mu\else \mkern 8mu\fi (#1)}
  {\mkern4mu(#1)}
  {\mkern4mu(#1)}
}

\usepackage{graphicx}

\usepackage[colorlinks=true,citecolor=black,linkcolor=black,urlcolor=blue]{hyperref}

\newcommand{\doi}[1]{\href{http://dx.doi.org/#1}{\texttt{doi:#1}}}
\newcommand{\arxiv}[1]{\href{http://arxiv.org/abs/#1}{\texttt{arXiv:#1}}}

% declare theorem-like environments
\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{fact}[theorem]{Fact}
\newtheorem{observation}[theorem]{Observation}
\newtheorem{claim}[theorem]{Claim}

\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{open}[theorem]{Open Problem}
\newtheorem{problem}[theorem]{Problem}
\newtheorem{question}[theorem]{Question}

\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}
\newtheorem{note}[theorem]{Note}
\usepackage{tikz}

\def\vf{\varphi}
%\def\begin{proof}{\par\noindent{\it Proof.\ \ }}
\def\qed{\ifmmode\square\else\nolinebreak\hfill
$\square$\fi\par\vskip12pt}
\def\rank{{\rm rank}}
\newcommand{\calC}{{\cal C}_{G}^b(n)}
\newcommand{\calW}{{\cal W}_{G}^b(n)}

\def\ov{\overline} \def\l{\langle} \def\r{\rangle} \def\tr{{\rm tr}}
\def\div{\,\Big|\,} \def\ddiv{\,\Big\Vert\,}\def\notdiv{{\,\not\Big|\,}}

\def\ZZ{{\cal Z}}
%\def\FF{\Bbb F} \def\ZZ{\Bbb Z}

\def\Aut{{\rm Aut}} \def\Inn{\rm Inn} \def\Out{\rm Out}
\def\Cay{{\rm Cay}}
\def\C{{\bf C}}\def\N{{\bf N}}\def\Z{{\bf Z}} \def\O{{\bf O}}

\def\Ga{\Gamma}
\def\a{\alpha} \def\b{\beta} \def\d{\delta}\def\g{\gamma} \def\s{\sigma}
\def\t{\tau} \def\va{\varepsilon}

\def\A{{\rm A}}\def\Sym{{\rm Sym}}

\def\PSL{{\rm PSL}}
\def\Fix{{\rm Fix}}
\def\rst{\!\!\restriction}



%\vskip 4in

\title{\bf Improved lower bounds for the\\ orders of even girth cages}
\author{Tatiana Baginov\' a Jajcayov\' a\thanks{Supported by VEGA 1/0577/14 and VEGA 1/0474/15.}\\
\small Comenius University \\[-0.8ex] 
\small Bratislava, Slovakia \\
\small\tt tatiana.jajcayova@fmph.uniba.sk\\
\and
Slobodan Filipovski\thanks{Supported in part by the Slovenian Research Agency (research program P1-0285 and Young Researchers Grant).}\\ 
\small University of Primorska\\[-0.8ex]
\small Koper, Slovenia\\
\small\tt slobodan.filipovski@famnit.upr.si\\
\and
Robert Jajcay\thanks{Supported by VEGA 1/0577/14, VEGA 1/0474/15, NSFC 11371307, and by the Slovenian Research Agency (research project J1-6720).}\\
\small Comenius University \\[-0.8ex] 
\small Bratislava, Slovakia \\
\small\tt robert.jajcay@fmph.uniba.sk
}

\date{\dateline{Mar 17, 2016}{Sep 9, 2016}{}\\
\small Mathematics Subject Classifications: 05C35, 05C38, 05C30}
         
\begin{document}        
\maketitle

\begin{abstract}
The well-known Moore bound $M(k,g)$ serves as a universal lower bound for the 
order of $k$-regular graphs of girth $g$. The excess $e$ of a $k$-regular graph $G$ of girth $g$
and order $n$ is the difference between its order $n$ and the 
corresponding Moore bound, $ e=n - M(k,g) $. We find infinite families of parameters
$ (k,g) $, $g > 6 $ and even, for which we show that the excess of any $k$-regular graph 
of girth $g$ is larger than $4$. This yields new improved lower bounds on the order of
$k$-regular graphs of girth $g$ of smallest possible order; the so-called $(k,g)$-cages. 
We also show that the excess of $k$-regular graphs of girth $g$
can be arbitrarily large for a restricted family of $(k,g)$-graphs satisfying an 
additional structural property and large enough $k$ and~$g$.

\bigskip\noindent \textbf{Keywords:} $k$-regular graphs, girth, cages, Moore bound, excess
\end{abstract}

\section{Introduction}
A $(k,g)$-{\em graph} is a $k$-regular graph of girth $g$. 
A $(k,g)$-{\em cage\/} is a smallest $(k,g)$-graph; its order is denoted by $n(k,g)$.
Infinitely many $(k,g)$-graphs for any degree/girth pair $(k,g)$ are known to exist since the 
1960's \cite{erdossachs,sachs}, however, the orders  $n(k,g)$ of $(k,g)$-cages
have only been
determined for very limited sets of parameters \cite{exojaj}.

The {\em Moore bound} $M(k,g)$ is a natural lower
bound on the order of $(k,g)$-graphs (and therefore also of the $(k,g)$-cages).
Its value depends on the parity of $g$:
\begin{equation} \label{moore1}
n(k,g) \ge  M(k,g) = \left\{
\begin{array}{lc} 1 + k + k(k-1) + \cdots + k(k-1)^{(g-3)/2},
                                                         & g \mbox{ odd, } \\
                              2 \left( 1 + (k-1) + \cdots + (k-1)^{(g-2)/2} \right),
                                                         & g \mbox{ even. }
\end{array}
\right.
\end{equation}

The order of the vast majority of $(k,g)$-cages is known to exceed the Moore
bound (e.g., \cite{exojaj}). 
The exact relation between $M(k,g)$ and $n(k,g)$ is however one of the
big open questions of the theory of cages.
Graphs whose orders equal the Moore bound are called
{\em Moore graphs} and are known to exist
if and only if $k=2$ and $ g \geq 3 $, $g=3$ and $ k \geq 2 $,
$g=4$ and $ k \geq 2 $, $g = 5$ and $k=2, 3, 7 $, or $g = 6, 8, 12$ and a generalized
$n$-gon of order $k-1$ exists \cite{banito,dam,exojaj}.
The existence of a $(57,5)$-Moore graph remains open. 

The difference between the order $n$ of a $(k,g)$-graph $G$ and the Moore
bound $M(k,g)$ is called the {\em excess} $e$ of the graph $G$, $e = n - M(k,g) $.
Determining the excess of $(k,g)$-cages is equivalent to determining $n(k,g)$.
As mentioned above, the exact values $n(k,g)$ are not known for the majority
of parameter pairs $(k,g)$, and very few lower bounds on $n(k,g)$ exceeding the 
Moore bound exist. Our entire knowledge of such lower bounds is limited to the 
following results.

%Brown \cite{brown} showed that $n(k,5)$ is never equal to $M(k,5)+1$.
%Eroh and Schwenk \cite{erosch} showed for $g=7$ the non-existence of 
%$k$-regular graphs of girth $7$ and order $M(k,7)+1$.
%(in comparison, $n(3,7)=M(3,7)+2 $, the order of the McGee graph). 
With regard to odd girths, 
Bannai and Ito \cite{Ban&Ito} have shown that no $k$-regular graphs of
order $M(k,g)+1$ exist for any odd $g \geq 5$. 
Kov\' acs \cite{kovacs} has shown that no graphs of excess $2$, girth $5$, and odd
degree $ k $ which is not of the form $ \ell^2 + \ell + 3 $ or $ \ell^2 + \ell - 1 $, 
where $ \ell $ is a positive integer, exist. 
Eroh and Schwenk \cite{erosch} proved that $n(k,5)$ is not equal to 
$M(k,5)+2$ for $5 \le k \le 11$. Most recent results concerning
odd girth and excess $2$ are due to Garbe \cite{garbe}. He showed
the non-existence of graphs of excess $2$ for parameters
$(k,9)$, $ (k,13) $, $ (k,17) $, $ (k,21) $, $ (k, 25) $, and $ (k,29) $ for certain 
congruence classes of $k$.
He also showed that there are no excess $2$ graphs in
the families of
$ (3,2s+1) $-graphs, $(7,2s+1)$-graphs, and $(9,2s+1)$-graphs,
for certain congruence classes of $s$.

Results concerning even girth are limited to the following
two theorems.

\begin{theorem}[\cite{bigito}]\label{bigito}
Let $G$ be a $(k,g)$-cage of girth
$g = 2m \geq 6$ and excess $e$.
If $e \leq k-2$, then $e$ is even and $G$ is bipartite of diameter $m + 1$.
\end{theorem}

For the next theorem, let $D(k,2)$ denote the  incidence graph of a symmetric $(v,k,2)$-design.
\begin{theorem}[\cite{bigito}]\label{excess2}
Let $G$ be a a $(k,g)$-cage of girth $g = 2m \geq 6$ and excess $2$.
Then $g=6$, $G$ is a double-cover of $D(k,2)$, and $k$ is not congruent to $5$ or $7  \pmod{8}$.
\end{theorem}

While Theorem~\ref{bigito} does not specifically exclude any parameter pairs $(k,g)$, 
Theorem~\ref{excess2} only deals with $(k,g)$-graphs of excess $2$. To our best knowledge,
outside some small cases for which $n(k,g)$ has been determined and some few cases where 
the existence of graphs of excess greater than $2$ has been proved by exhaustive computer 
search, no results excluding parameter pairs for excess larger than $2$ for either odd or even $g$ 
are known (i.e., there are no infinite families of pairs $(k,g)$ for which it has been proven that 
$ n(k,g) > M(k,g) + 4 $).
Thus, results obtained in this paper, which introduce infinite families of parameter pairs 
$(k,g)$ for which 
do not exist any $(k,g)$-graphs of excess smaller than $5$, are the first
results of this type. 

Our arguments rely
on the following fairly obvious lemma.
Let $G$ be 
a $k$-regular graph of girth $g$. For any given edge $f \in E(G)$ and integer $c \geq 3$,
let $ \overline{\bf c}_G(f,c) $ denote the {\em number of cycles} of length $c$ in $G$
containing  $f$.

\begin{lemma}\label{cycles-edges}
Let $G$ be a graph and $c \geq 3$. The sum
\[ \sum_{f \in E(G)} \overline{\bf c}_G(f,c) \]
is divisible by $c$.
\end{lemma}

The remaining argument is based on careful counting of cycles of length $g$ in 
(potential) $(k,g)$-graphs of excess $4$, 
and showing that, for certain classes of parameters, the resulting numbers violate the divisibility 
requirements of Lemma~\ref{cycles-edges}.
This type
of reasoning was for the first time used in \cite{fri}, as well as independently in \cite{jajsir}.
We have also used this idea in \cite{BagFil&Jaj}, which however only deals with graphs of excess not
exceeding $3$.
In addition to obtaining results concerning graphs of excess $4$, we prove in the last part
of our paper that the excess
grows without bounds for a meaningful but restricted family of $(k,g)$-graphs. While this
last result does not appear suitable for generalization to all $(k,g)$-graphs,
it should be viewed as further evidence for the Moore bound not being a tight 
bound in the majority of cases.

\section{The structure of graphs of even girth and excess $4$}
In this section, we take on the case of
$(k,g)$-graphs of degree $ k \geq 6 $, {\em even} girth $ g = 2m \geq 6 $, and excess $4$.
All of these graphs are covered by Theorem~\ref{bigito} and are
therefore bipartite and of diameter $ m+1 $. Thanks to these results,
the structure of $G$ with respect to any edge $f = \{ u,v \}  \in E(G)$ can therefore be determined. Let $N_G(u,i)$ denote the 
$i$-th neighborhood of the vertex $u$, i.e., the set of vertices of $G$ whose distance from $u$ in $G$ 
is equal to $i$. Since the girth of $G$ is assumed to be equal to $g$, the set of vertices of $G$
whose distance from $u$ is not larger than $\frac{g-2}{2}$ and whose distance from $v$ is by one
larger than their distance from $u$ and the set of of vertices of $G$
whose distance from $v$ is not larger than $\frac{g-2}{2}$ and whose distance from $u$ is by one
larger than their distance from $v$ must be disjoint and cannot contain any cycles. Thus, the 
subgraph of $G$ induced by the first set (determined by $u$) induces a tree of depth $\frac{g-2}{2}$ rooted at $u$ (we will  call
it ${\mathcal T}_u$), while
the second set induces a tree of depth $\frac{g-2}{2}$ rooted at $v$ (called ${\mathcal T}_v $); with $ {\mathcal T}_u $ and $ {\mathcal T}_v $ vertex disjoint. 
The degrees of $u$ or $v$ in their respective trees are equal to $(k-1)$, the 
degrees of all the non-leave vertices of these trees are equal to $k$, and all the leaves of these 
trees are of distance $\frac{g-2}{2}$ from their respective roots. As for the order of these subtrees,
they are both of order $ 1 + (k-1) + (k-1)^2 + \ldots +(k-1)^{\frac{g-2}{2}} $, with $(k-1)^i$ vertices
of distance $i$ from $u$ (or $v$).
We will call the union of $ {\mathcal T}_u $ and $ {\mathcal T}_v $ together with the edge $f$ the {\em Moore tree of $G$ rooted at $f$}; it is the subtree of $G$ that
is the basis of the Moore bound for even $g$.
Since $G$ is assumed to be of excess $4$, $G$
must contain $4$ additional vertices $ w_1,w_2,w_3,w_4 $ which do not belong to either $ {\mathcal T}_u $
or $ {\mathcal T}_v $, and whose distance from both $u$ and $v$ is greater than $\frac{g-2}{2}$.
We will call these vertices {\em the excess vertices with respect to $f$} and denote this set 
$ X_f = \{ w_1,w_2,w_3,w_4 \} $. Finally, we shall call the edges not contained in the Moore tree
of $G$ {\em horizontal edges}. The choice of our terminology becomes fairly obvious when consulting Figure 1.

\begin{figure}\label{moore-tree-even-girth}
\centering
\begin{tikzpicture}[scale=0.42],line width=.5mm]
\tikzstyle{every node}=[draw,circle,fill=black,minimum size=5pt,
                            inner sep=0pt]
     \node (1tt) at (0,0) {};
     \node (1tl) at (-2,2) {};
     %\node (1tc) at (0,2) {};
     \node (1tr) at (2,2) {}; 
     \node (1tl1) at (-4,4) {}; 
     \node (1tl3) at (-1,4) {}; 
     %\node (1tc1) at (-1,4) {}; 
     %\node (1tc3) at (1,4) {}; 
     \node (1tr1) at (1,4) {}; 
     \node (1tr3) at (4,4) {}; 
     \draw[line width=.5mm] (1tt) -- (1tl);
     %\draw[line width=.5mm] (1tt) -- (1tc);
     \draw[line width=.5mm] (1tt) -- (1tr);
     \draw[line width=.5mm] (1tl) -- (1tl1);
     \draw[line width=.5mm] (1tl) -- (1tl3);
     %\draw[line width=.5mm] (1tc) -- (1tc1);
     %\draw[line width=.5mm] (1tc) -- (1tc3);
     \draw[line width=.5mm] (1tr) -- (1tr1);
     \draw[line width=.5mm] (1tr) -- (1tr3);
     
     \node (2tt) at (9,0) {};
     \node (2tl) at (7,2) {};
     %\node (1tc) at (0,2) {};
     \node (2tr) at (11,2) {}; 
     \node (2tl1) at (5,4) {}; 
     \node (2tl3) at (8,4) {}; 
     %\node (1tc1) at (-1,4) {}; 
     %\node (1tc3) at (1,4) {}; 
     \node (2tr1) at (10,4) {}; 
     \node (2tr3) at (13,4) {}; 
     \draw[line width=.5mm] (2tt) -- (2tl);
     %\draw[line width=.5mm] (1tt) -- (1tc);
     \draw[line width=.5mm] (2tt) -- (2tr);
     \draw[line width=.5mm] (2tl) -- (2tl1);
     \draw[line width=.5mm] (2tl) -- (2tl3);
     %\draw[line width=.5mm] (1tc) -- (1tc1);
     %\draw[line width=.5mm] (1tc) -- (1tc3);
     \draw[line width=.5mm] (2tr) -- (2tr1);
     \draw[line width=.5mm] (2tr) -- (2tr3);
     \draw[line width=.5mm] (1tt) -- (2tt);
     \draw[very thick](1tl1) .. controls (-3.7,11) and (12.7,11) .. (2tr3);
     \draw[very thick](1tr3) .. controls (4.3,4.5) and (4.7,4.5) .. (2tl1);
     \draw[very thick](1tl1) .. controls (-3.7,5.5) and (4.7,5.5) .. (2tl1);
     %\draw[very thick](1tl3) .. controls (-0.7,6.5) and (7.7,6.5) .. (2tl3);
     \draw[very thick](1tl3) .. controls (-0.7,5) and (9.7,5) .. (2tr1);
     \draw[very thick](1tr1) .. controls (1.3,6) and (7.7,6) .. (2tl3);
     \draw[very thick](1tr1) .. controls (4.3,6) and (12.5,6) .. (2tr3);
     %\draw[very thick](1tr3) .. controls (4.3,5.5) and (9.7,5.5) .. (2tr1);
     %\draw (-4.5,-0.5) rectangle +(18,5);
     \node (w1) at (3.5,8) {};
     \node (w2) at (3.5,6.5) {};
     \node (w3) at (5.5,8) {};
     \node (w4) at (5.5,6.5) {};
     \draw[line width=.5mm] (w1) -- (w3);
     \draw[line width=.5mm] (w2) -- (w4);
     \draw[line width=.5mm] (1tl3) -- (w1);
     \draw[line width=.5mm] (1tr3) -- (w2);
     \draw[line width=.5mm] (2tl3) -- (w4);
     \draw[line width=.5mm] (2tr1) -- (w3);
     \tikzstyle{every node}=[draw,circle,fill=black,minimum size=0pt,
                            inner sep=0pt]
     \draw[line width=.5mm] (17,0) node (3tt) [label=above:Moore tree] {};
     \draw[line width=.5mm] (17,1.9) node (3tt) [label=above:horizontal edges] {};
     \draw[line width=.5mm] (0,-0.5) node (3tt) [label=below:$u$] {};
     \draw[line width=.5mm] (9,-0.5) node (3tt) [label=below:$v$] {};
     \draw[line width=.5mm] (4.5,0.1) node (3tt) [label=above:$f$] {};
     \draw[line width=.5mm] (3.2,8.3) node (w1) [label=left:$w_1$] {};
     \draw[line width=.5mm] (3.2,6.1) node (w2) [label=left:$w_2$] {};
     \draw[line width=.5mm] (5.8,8.3) node (w3) [label=right:$w_3$] {};
     \draw[line width=.5mm] (6.0,6.1) node (w4) [label=right:$w_4$] {};
     \draw[line width=.5mm] (1,7) node (w4) [label=left:$\vdots$] {};
     \draw[line width=.5mm] (8,7) node (w4) [label=right:$\vdots$] {};
     \draw[line width=.5mm] (-1,2) node (w4) [label=right:${\mathcal T}_u$] {};
     \draw[line width=.5mm] (8,2) node (w4) [label=right:${\mathcal T}_v$] {};
     \draw[line width=.5mm] (4.5,8.1) node (w4) [label=below:$X_e$] {};
     \draw (-4.5,-0.5) rectangle +(18,5);
     \draw (3.1,6.2) rectangle +(2.8,2.1);
\end{tikzpicture}
\caption{The Moore tree and some of the horizontal edges in a 
potential $(3,6)$-graph of excess $4$}
\end{figure}


We begin with a lemma that restricts the possible ways in which the
four excess vertices are attached to the Moore tree.

\begin{lemma}\label{lemma4}
Let $ k \geq 6 $, $ g = 2m \geq 6 $. Let $G$ be a $(k,g)$-graph
of excess $4$, $u,v$ be two adjacent vertices in $G$, and $ X_f = \{ w_1,w_2,w_3,
w_4 \} $
be the four excess vertices with respect to the edge $ f = \{ u,v \} $. The
induced subgraph $ G[w_1,w_2,w_3,w_4] $ is isomorphic to $ 2K_2$
(two disjoint copies of $K_2$) or ${\mathcal P}_3$ (a path of length $3$).
\end{lemma}
\begin{proof}
As shown in Figure 1, 
the graph $G$ consists of a Moore tree rooted at the edge $ f= \{ u,v \} $ and four
excess vertices $ w_1,w_2,w_3,w_4 $. Each of these vertices must be
attached to at least one of the two subtrees rooted at $u$ or $v$ (for the
graph to be of diameter $m+1$), and none can be attached to both, since
$G$ is bipartite (and the leaf sets of $ {\mathcal T}_u $ and $ {\mathcal T}_v $
belong to different bipartite sets). 
Furthermore, none of the excess vertices can be joined to its corresponding
subtree via more than $(k-1)$ edges; this is due to the fact that the excess 
vertices cannot be joined to any branch of the subtree more than once as 
multiple attachments would give rise to a cycle shorter than $g$, and 
to the fact that the subtrees $ {\mathcal T}_u $ and $ {\mathcal T}_v $ each consist of 
exactly $(k-1)$ branches. 

The horizontal edges of $G$ are of three kinds.
First, there are the horizontal edges directly joining the leaf sets of 
$ {\mathcal T}_u $ and $ {\mathcal T}_v $. Second, there are the horizontal
edges between the excess vertices $ w_1,w_2,w_3,w_4 $ and 
the leaf sets of $ {\mathcal T}_u $ or $ {\mathcal T}_v $ (but never simultaneously
with both). 
Finally, there are the horizontal edges between the excess vertices themselves.
Note that the number
of edges incident with the leaves of $ {\mathcal T}_u $ must match the 
number of edges incident with the leaves of $ {\mathcal T}_v $.
Thus, in order to balance and pair out the horizontal edges adjacent to the 
two leaf sets,
the number of edges joining the excess vertices to either of the two subtrees
must be the same. This easily yields that two of the excess vertices must be
attached to one subtree and the other two to the other, and the two pairs
belong to different bipartite sets. Without loss of generality, assume that
$w_1,w_2$ are attached to the subtree rooted at $u$, and
$w_3,w_4$ to the subtree rooted at $v$ (Figure 1).
Due to bipartedness, $w_1$ is not adjacent to $w_2$, and $w_3$ is not adjacent to $w_4$. Since the diameter of $G$ is $m+1$, both $w_1$ and $w_2$ must
be adjacent to at least one of $w_3,w_4$, and vice versa,
both $w_3$ and $w_4$ must be adjacent to at least one of $w_1,w_2$.
It follows that the induced subgraph $ G[w_1,w_2,w_3,w_4] $ is bipartite,
with the two sets consisting of $ w_1,w_2 $ and $ w_3, w_4 $, and each of its
vertices is of degree at least $1$. This leaves us with the possibility that all of
its vertices are of degree $1$, and hence $ G[w_1,w_2,w_3,w_4] $ is
isomorphic to $2K_2$; one vertex in each set is of degree $1$ and one is of
degree $2$, and $ G[w_1,w_2,w_3,w_4] $ is isomorphic to ${\mathcal P}_3$;
or all of it vertices are of degree $2$, in which case $ G[w_1,w_2,w_3,w_4] $ is
isomorphic to the $4$-cycle, which contradicts the assumption that the girth of $G$ is at
least $6$.
\end{proof}

The number of cycles through any edge of the graph depends now on the form of $ G[w_1,w_2,w_3,w_4] $.

\begin{lemma}\label{4count}
Let $ k \geq 6 $, $ g = 2m \geq 6 $. Let $G$ be a $(k,g)$-graph
of excess $4$, $u,v$ be two adjacent vertices in $G$, $ f $ be the edge $ \{ u,v \} $, and $ w_1,w_2,w_3,w_4 $
be the four excess vertices with respect to $ f $.
\begin{enumerate}
\item if $ G[w_1,w_2,w_3,w_4] $ is isomorphic to $2K_2$, then
$ \overline{\bf c}_G(f,g) = (k-1)^m - 2k +2 $;
\item if $ G[w_1,w_2,w_3,w_4] $ is isomorphic to ${\mathcal P}_3$, then
$ \overline{\bf c}_G(f,g) = (k-1)^m - 2k + 3$.
\end{enumerate}
\end{lemma}
\begin{proof}
Let us assume again that $w_1,w_2$ are attached to the subtree rooted at $u$, and $w_3,w_4$ to the subtree 
rooted at $v$.

If $ G[w_1,w_2,w_3,w_4] $ is isomorphic to $2K_2$, the number of
edges between $w_1,w_2$ and the corresponding leaves of the Moore tree
is $ 2(k-1) $. Thus, the number of horizontal edges between the two sets of
leaves of the Moore tree is equal to $ (k-1)^m - 2(k-1) $ (with $(k-1)^m$ being the
number of horizontal edges in a (potential) $(k,g)$-Moore graph).
As pointed out before, each horizontal edge corresponds to exactly
one $g$-cycle through $f$, and no other $g$-cycles through $f$ exist. Thus,
$ \overline{\bf c}_G(f,g) = (k-1)^m - 2(k-1) $.

If $ G[w_1,w_2,w_3,w_4] $ is isomorphic to ${\mathcal P}_3$, the
number of horizontal edges between the two sets of
leaves of the Moore tree is equal to $ (k-1)^m - (k-1) - (k-2) $, and the result
follows in exactly the same way as above.
\end{proof}

In order to employ the above formulas, we would have to find significant restrictions on the number of edges of one type or the other. On the 
other hand, it is easy to find arithmetic conditions on $k$ and $g$  
that exclude the existence of `non-mixed' $(k,g)$-graphs of order $M(k,g)+4$ 
(by non-mixed we mean graphs that contain only edges 
for which $ G[w_1,w_2,w_3,w_4] $ is isomorphic to $2K_2$ or only
edges for which
$ G[w_1,w_2,w_3,w_4] $ is isomorphic to ${\mathcal P}_3$, but not both). 
Hence, the situation
appears similar to that of the odd-girth graphs of excess $2$. 
Fortunately, this is not the case. In what follows, we show that
even-girth graphs of excess $4$ and girth larger than $6$ cannot be mixed when it comes to counting cycles of length $g$.

We begin our argument by counting $g$-cycles passing through vertices. 
In order to do this, we have to subdivide one of the possibilities considered above for 
edges (the case $2K_2$). For the first time, this will turn to our advantage.

Let $u$ be a vertex of $G$ incident with an edge $f = \{ u,v \} $ for which the subgraph 
induced by $X_f$ is isomorphic to $2K_2$. Two of the vertices in $X_f$ are then of
distance $\frac{g}{2}$ from $u$ (let us denote them $ w_1,w_2 $) and two of them are of distance 
$ \frac{g+2}{2} $ from $u$ (say, $ w_3,w_4$). The vertices $w_3$ and $w_4$ either share a neighbor 
(which necessarily has to belong to the set of vertices of distance $\frac{g-2}{2}$ from $v$),
or they do not share a neighbor.  It is important to note that if $g$ is assumed to be greater 
than $4$, $w_3,w_4$ cannot share more than one neighbor as that would lead to a $4$-cycle.
We say that $u$ is of the {\em first $2K_2$ type} if $w_3,w_4$
share a neighbor, and we say that $u$ is of the {\em second $2K_2$ type} if they do not.
Having defined the types, we can now state the first lemma the proof of which
is quite elementary. In analogy with 
the notation introduced previously for edges, 
${\bf c}_G(u,g)$ stands for the {\em number of $g$-cycles in $G$ rooted at the 
vertex} $u$. 

\begin{lemma}\label{4count-vertex}
Let $ k \geq 6 $, $ g = 2m \geq 6 $. Let $G$ be a $(k,g)$-graph
of excess $4$ and $u$ be a vertex of $G$. Then,
\begin{enumerate}
\item if $u$ is of the first $2K_2$ type, then
\[ {\bf c}_G(u,g) =
 ((k-1)^m - 2k +2) + ((k-1)^{m-1}-2k) \cdot {k-1 \choose 2} + k^3-4k^2+5k-1 ; \]
\item if $u$ is of the second $2K_2$ type, then
\[ {\bf c}_G(u,g) = ((k-1)^m - 2k +2) + ((k-1)^{m-1}-2k) \cdot {k-1 \choose 2} + 
k^3 - 4k^2 + 5k - 2 ; \]
\item if $u$ is incident with an edge $f$ whose excess set $X_f$ 
is isomorphic to ${\mathcal P}_3$, then
\[ {\bf c}_G(u,g) =
 ((k-1)^m - 2k +3) + ((k-1)^{m-1}-2k) \cdot {k-1 \choose 2} + 
k^3-4k^2+5k-2. \]
\end{enumerate}
\end{lemma}
\begin{proof}
Let $u$ be of the first $2K_2$ type with respect to the edge $f= \{ u,v \} $. The $g$-cycles passing through $u$ come in two kinds.
First, there are the $(k-1)^m - 2k +2$ $g$-cycles containing $f$ as claimed in Lemma~\ref{4count}.
Then there are $g$-cycles containing $u$ but avoiding $f$. All of them have to consist of two
disjoint $ \frac{g-2}{2}$-paths starting at $u$ and connected through a pair of edges attached to 
vertices of distance $ \frac{g}{2}$ from $u$ (the endpoints of the two paths) that share a vertex.
The choice of these two final edges completely determines the $g$-cycles, so we will count the 
possible pairs of such edges. Both $w_1$ and $w_2$ are adjacent to $k-1$ vertices of 
distance $ \frac{g-2}{2}$ from $u$, which gives us $ 2 {k-1 \choose 2} $ $g$-cycles through $w_1$
or $w_2$. Of the $(k-1)^{\frac{g-2}{2}}$ vertices of distance $\frac{g-2}{2}$ from $v$, 
there is one adjacent to both vertices $w_3,w_4$, 
%(and not more, as we assume $ g \geq 6 $),
there are $ 2(k-2) $ vertices adjacent to exactly one of the vertices $w_3,w_4$, and the rest 
are not adjacent to either $w_1$ or $w_2$. It follows that the vertex adjacent to both $w_3$ and 
$w_4$ is incident with $k-3$ horizontal edges, and is therefore contained in $ {k-3 \choose 2} $
$g$-cycles rooted at $u$. The other $2(k-2)$ vertices give rise to $2 {k-2 \choose 2}$ $g$-cycles,
and all the remaining vertices contribute $((k-1)^{\frac{g-2}{2}}-2k+3) {k-1 \choose 2} $ $g$-cycles
through $u$.
Adding all these cycles yields
\begin{align*} 
{\bf c}_G(u,g) &=
((k-1)^m - 2k +2) + ((k-1)^{m-1}-2k+3) \cdot {k-1 \choose 2} \\
&\quad+(2k-4){k-2 \choose 2} + {k-3 \choose 2} + 2 {k-1 \choose 2},
\end{align*}
which matches the quantity claimed in Case 1.

If $u$ is of the second $2K_2$ type, the situation differs only in a few spots. First, there are the 
$(k-1)^m - 2k +2$ $g$-cycles containing $f$. The $g$-cycles not containing $f$ contain either
one of the $w_1,w_2$, and there are $ 2 {k-1 \choose 2} $ of those, or they pass through the 
$ 2k-2 $ vertices of distance $ \frac{g-2}{2}$ from $v$ and adjacent to $ w_3 $ or $ w_4 $, 
which contribute $ (2k-2){k-2 \choose 2} $ cycles, or they pass through vertices
of distance $ \frac{g-2}{2}$ from $v$ adjacent to neither $ w_3 $ nor $ w_4 $ which finally contribute
$((k-1)^{\frac{g-2}{2}}-2k+2) {k-1 \choose 2} $ $g$-cycles through $u$. Thus,
\[ {\bf c}_G(u,g) = ((k-1)^m - 2k +2) + ((k-1)^{m-1}-2k+2) \cdot {k-1 \choose 2} + 
(2k-2){k-2 \choose 2} + 2 {k-1 \choose 2}, \]
and simple arithmetic yields the claim in Case 2.

Assume finally that $u$ is incident with an edge $f = \{ u,v \} $ whose excess set $X_f$ 
is isomorphic to ${\mathcal P}_3$. Without loss of generality we may assume that $w_1$ is
the vertex adjacent to both $w_3$ and $w_4$.
In a way similar to the argument preceding this proof, the vertices
$w_3,w_4$ cannot share a neighbor among the vertices of distance $ \frac{g-2}{2}$ from $v$:
they already share one neighbor, $w_1$, 
and the existence of another shared neighbor would cause the existence of a $4$-cycle. 
The counting of cycles through $u$ now follows the usual lines. There are 
$ ((k-1)^m - 2k + 3) $ cycles containing $f$ (Lemma~\ref{4count}), $ {k-2 \choose 2} $ cycles
containing $w_1$, $ {k-1 \choose 2} $ cycles containing $w_2$, 
$ (2k-3){k-2 \choose 2} $ cycles through the vertices of distance $ \frac{g-2}{2}$ from $v$ that are
adjacent to $w_3$ or $w_4$, and  $ ((k-1)^{m-1}-2k+3) \cdot {k-1 \choose 2} $ cycles through 
the vertices of distance $ \frac{g-2}{2}$ from $v$ that are not adjacent to $w_3$ or $w_4$:
\begin{align*}
{\bf c}_G(u,g) &= 
((k-1)^m - 2k +3) + ((k-1)^{m-1}-2k+3) \cdot {k-1 \choose 2}\\ 
&\quad+ (2k-3){k-2 \choose 2} + {k-2 \choose 2} + {k-1 \choose 2}.% &&\qed
\end{align*}
\end{proof}

A simple comparison of the three cases in Lemma~\ref{4count-vertex} yields that 
the first and the third numbers match while the second is by one smaller than the other 
two. This means that no vertex can be simultaneously incident to edges from the first and
second part or the second and third part 
(since the number of cycles through a vertex has to be
unique). 
This simple observation has a very strong consequence.

\begin{lemma}\label{nomess}
Let $ k \geq 6 $, $ g = 2m > 6 $, and let $G$ be a $(k,g)$-graph
of excess $4$. Then, $G$ does not contain edges $f$ for which their
corresponding excess set $X_f$ induces a subgraph isomorphic to ${\mathcal P}_3$.
\end{lemma}
\begin{proof}
Suppose that $G$ satisfies the above conditions, and, by means of contradiction,
assume that the excess set $X_f$ induces a subgraph isomorphic to ${\mathcal P}_3$
for some edge $f$ of $G$. Let us stress right away that we are assuming that 
$ g > 6 $ and therefore $G$ does not contain cycles of length $4$ or $6$.

Let $f = \{ u,v \} $, $X_f=\{ w_1,w_2,w_3,w_4 \} $, and the 
vertices adjacent to $u$ but distinct from $v$ be denoted by $ v_1,v_2, \ldots, v_{k-1} $.
Also, without loss of generality, assume that $w_1$ and $w_2$ are of distance 
$ \frac{g}{2} $ from $u$ and the vertex adjacent to both $w_3$ and $w_4$ is the vertex 
$w_2$. The number of edges connecting $w_2$ to the branch of height $ \frac{g-2}{2} $
rooted at $u$ is then $k-2$, and therefore $w_2$ is not attached to one of the 
sub-branches rooted at the neighbors  $ v_1,v_2, \ldots, v_{k-1} $ (i.e., $w_2$ is of 
distance greater than $ \frac{g-2}{2} $ from one of the vertices $ v_1,v_2, \ldots, v_{k-1} $).
Again without loss of generality, we may assume that this special vertex is the vertex 
$v_1$. Let $f'$ be the edge $\{ u,v_1 \}$. Since the distance of $w_2$ from 
$v_1$ is greater than $\frac{g}{2}$, the excess of $f'$ contains the vertex $w_2$ together 
with the vertices $w_3,w_4$. It follows that the subgraph 
induced by $X_{f'}$ contains $w_2,w_3$ and $w_4$ and since 
$w_2$ is adjacent to both $w_3$ and $w_4$, the degree of $w_2$ in
the induced subgraph must be $2$, and hence the subgraph induced by $f' = \{ u,v_1 \}$ must be  isomorphic to $ {\mathcal P}_3 $.

Next let $f''$ be the edge $\{ u,v_2 \}$. Then both $w_1$ and $w_2$ are of distance 
$ \frac{g-2}{2} $ from $v_2$, and it is easy to see that the excess set of $f''$ must
consist of the vertices $ w_3,w_4 $ and two vertices $w_5,w_6$ belonging to the branch rooted at $v$, of distance $ \frac{g-2}{2} $ from $v$.
We claim that the subgraph induced
in $G$ by the set $X_{f''} = \{ w_3,w_4,w_5,w_6 \} $ cannot be isomorphic to 
${\mathcal P}_3$, as this would give rise to a $4$-cycle formed by the vertices
$w_2,w_3,w_5,w_4$ or the vertices $w_2,w_3,w_6,w_4$, 
depending on whether $w_5$ or $w_6$ 
would be of degree $2$ in the induced subgraph. Hence, the subgraph of $G$ induced
by $X_{f''}$ is isomorphic to $2K_2$. We further claim that the vertices $w_5,w_6$
cannot share a neighbor, as if they did share a neighbor, this would give rise to a 
$6$-cycle formed of the vertices $w_2,w_3,w_4,w_5,w_6$ and the shared neighbor.
We conclude that the edge $f'' = \{ u,v_2 \} $ is of the second $2K_2$ type. This means that $u$ is incident to 
$ f' = \{ u,v_1 \} $ for which the subgraph induced by $ X_{f'} $
is isomorphic to $ {\mathcal P}_3 $ and to $ f'' = \{ u, v_2 \} $ which
of the second $2K_2$ type.
However, as pointed out in the discussion preceding this lemma, no vertex of $G$
can be incident with an edge whose excess set induces $ {\mathcal P}_3$ and 
and at the same time with an edge of the second $2K_2$ type. 
Therefore $G$
cannot contain an edge whose excess set induces $ {\mathcal P}_3$.
\end{proof}

\section{Excluding parameter pairs for even girth and excess $4$}

Combining Lemma~\ref{nomess} with Lemma~\ref{4count}
immediately yields:
\begin{lemma}\label{finally}
Let $ k \geq 6 $, $ g = 2m > 6 $, and let $G$ be a $(k,g)$-graph
of excess $4$. Then $g$ divides the number 
\begin{equation} \label{eq1}
\frac{(M(k,g)+4)\cdot k}{2} \cdot ((k-1)^m - 2k +2). 
\end{equation} 
\end{lemma}

In order to employ this lemma and to exclude some parameter pairs $(k,g)$
for which no $(k,g)$-graphs of excess $4$ exist, we derive a number
of simple divisibility results.

\begin{lemma}\label{arithm}
Let $ k \geq 6 $ and $ g = 2m > 6 $.
\begin{enumerate}
\item If  $g=2p$ such that $p > 3 $ is prime number and $ k \not \equiv 1,2 \pmod{p} $,
then $M(k,g)+4\equiv6 \pmod {p}.$
\item If $g=4\cdot3^{s}$ such that $s\geq1$ and $k$ is divisible by $9$, then 

$ M(k,g)+4\equiv4\pmod {3^{s}}.$
\item If $g=2p^{2}$ such that $p\geq3 $ is a prime number and $k$ is an even number,
$ k \not \equiv 1,2 \pmod{p} $, then $ M(k,g)+4\equiv6 \pmod {p}.$
\item If $g=4p$ such that $p\geq3 $ is a prime number and  $ k \not \equiv 1,2 \pmod{p} $, then $ M(k,g)+4\equiv2k+4 \pmod {p}.$
\item If $k\equiv3  \pmod {g}$, then $M(k,g)+4\equiv 2\cdot2^{g/2}+2 \pmod{g}$.
\end{enumerate}
\end{lemma}

\begin{proof}
We proceed case by case.
\begin{itemize} 
\item[{\rm (1)}] Let $ M(k,g)\equiv r  \pmod {p}.$ Since $M(k,g)=2\left(\frac {(k-1)^{g/2}-1}{k-2}\right)$ and $(k-2,p)=1$,  \\ we get 
$$2((k-1)^{g/2}-1)\equiv r(k-2) \pmod {p}.$$
Since $(k-1,p)=1$, Fermat's Little Theorem asserts $(k-1)^{p}\equiv k-1 \pmod {p}.$ 
Thus, $(k-2)(r-2)\equiv 0  \pmod {p}.$ Due to the second restriction we have chosen for $k$,
$p$ does not divide $k-2$, and therefore it must divide $r-2$. Hence, $ r\equiv 2  \pmod {p}$,
which means that $ M(k,g)+4\equiv 6  \pmod {p}.$
\item[{\rm (2)}] Let $ M(k,g)\equiv r  \pmod{3^{s}}.$ Since $(k-2,3^{s})=1$. As above,
we obtain
$$ 2((k-1)^{g/2}-1)\equiv r(k-2) \pmod {3^{s}}.$$
Since $(k-1, 3^{s})=1 $ and the Euler's totient function value $ \varphi(3^{s})=2\cdot 3^{s-1}$, Euler's Theorem yields
$$ 2((k-1)^{g/2}-1)\equiv 2((k-1)^{2\cdot3^{s}}-1)\equiv 2(1-1)\equiv 0 \pmod {3^{s}}.$$
Thus, $(k-2)r\equiv 0 \pmod {3^{s}}$, and consequently, $ r\equiv0 \pmod {3^{s}}.$ Therefore $ M(k,g)+4\equiv 4 \pmod {3^{s}}.$
\item[{\rm (3)}] Following the same line of argument as above, $2((k-1)^{g/2}-1)\equiv r(k-2) \pmod {p}.$ Since $(2,p^2)=1$, using the multiplicativity of Euler's function we obtain
$$  \varphi(g)=\varphi(2p^{2})=\varphi(2)\cdot\varphi(p^2)=p^{2}(1-\frac{1}{p})=p^{2}-p.$$
Since $(k-1,g)=1$, applying Euler's Theorem implies $(k-1)^{\varphi(g)}\equiv(k-1)^{p^{2}-p}\equiv1\pmod {g}$ i.e. $(k-1)^{p^{2}}\equiv(k-1)^{p} \pmod {g}.$
Thus, $r(k-2)\equiv2((k-1)^{p}-1) \pmod {g}$, and hence, $r(k-2)\equiv2(k-2) \pmod {p}.$
Since $(k-2,p)=1$, $r\equiv 2  \pmod {p}$, and $M(k,g)+4\equiv6  \pmod{p}.$
\item[{\rm (4)}] Applying Fermat's Little Theorem yields $(k-1)^{g/2}\equiv(k-1)^{2p}\equiv((k-1)^{p})^{2}\equiv (k-1)^{2} \pmod {p}.$
Therefore, $ 2((k-1)^{g/2}-1))\equiv2(k^{2}-2k+1-1)\equiv 2k(k-2) \pmod {p}.$ From this follows that $(k-2)(r-2k)\equiv0 \pmod {p}$ i.e.
$r\equiv2k \pmod {p}, M(k,g)+4\equiv2k+4 \pmod {p}.$
\item[{\rm (5)}] Since $k-2 \equiv 1  \pmod {g}$, $ M(k,g)\equiv2((k-1)^{g/2}-1)\equiv2\cdot2^{g/2}-2 \pmod {g}$, i.e
$M(k,g)+4\equiv2\cdot2^{g/2}+2 \pmod{g}.$
\end{itemize}
This completes the proofs for all cases of the lemma.
\end{proof}

We are finally ready to exclude infinite families of parameter pairs.
\begin{theorem}\label{exclude}
Let $ k \geq 6 $, $ g = 2m > 6 $. No $(k,g)$-graphs of excess $4$ exist for parameters
$k,g$ satisfying at least one of the following conditions:
\begin{itemize}
\item[{\rm (1)}] $g=2p$, with $p\geq5$ a prime number, and $k \not \equiv 0, 1, 2  \pmod{p}$;
\item[{\rm (2)}] $ g=4\cdot3^{s}$ such that $ s\geq 4 $, and $k$ is divisible by $9$ but not by $ 3^{s-1}$;
\item[{\rm (3)}]  $ g=2p^{2}$ with $p\geq 5$ a prime number, and  $k \not \equiv 0, 1, 2  \pmod{p}$ and even; 
\item[{\rm (4)}] $ g=4p$, with $p\geq 5 $ a prime number, and  $k \not \equiv 0, 1, 2,3,p-2  \pmod{p}$;
\item[{\rm (5)}] $g\equiv0 \pmod {16}$, and $k\equiv3 \pmod {g}.$
\end{itemize}
\end{theorem}



\medskip

\begin{proof}
Each of the cases of our proof starts  by assuming that 
there exists a $(k,g)$-graph $G$ of order $M(k,g)+4$ whose parameters satisfy the 
corresponding conditions, after which we derive a contradiction with the 
divisibility of (\ref{eq1}) by $g$ from Lemma~\ref{finally}.
\begin{itemize}
\item[{\rm (1)}] 
%Lemma~\ref{finally} yields
%\begin{equation}\label{eq1}
%\left(\frac {M(k,g)+4}{2}\right)k((k-1)^{p}-2(k-1))\equiv 0  \pmod {p}. 
%\end{equation}
Lemma~\ref{arithm} together with $(2,p)=1$ yield $\frac {M(k,g)+4}{2}\equiv 3  \pmod {p}.$ 
Since $p$ divides neither $k$ nor $k-1$, $ k((k-1)^{p}-2(k-1))\equiv -k(k-1) \not \equiv 0  \pmod {p}.$ Hence, neither factor of the left side of (\ref{eq1}) is congruent to $0 \pmod{2p} $, which contradicts (\ref{eq1}).

\item[{\rm (2)}] Lemma~\ref{arithm} forces $ \frac {M(k,g)+4}{2}\equiv  
2  \pmod {3^s}.$
Since $ \varphi(3^s)=2\cdot3^{s-1}$, using Euler's Theorem, we obtain
$(k-1)^{2\cdot3^{s-1}}\equiv 1  \pmod {3^{s}}$, and consequently,
$ k((k-1)^{2\cdot3^{s}}-2(k-1))\equiv -k(2k-3)  \pmod {3^{s}}$. 
Since $k$ is not divisible by  $3^{s-1}$, and since $k \equiv 0  \pmod{9}$ yields that
$ 2k-3 $ is not divisible by $9$, the product $ -k(2k-3) \not \equiv 0   \pmod {3^{s}}$,
and we obtain a contradiction with (\ref{eq1}) again.

\item[{\rm (3)}] The assumptions and Lemma~\ref{arithm} imply 
$ \frac{M(k,g)+4}{2}\equiv 3 \pmod {p}$.
Since $(k-1,p)=1$, using Euler's Theorem gives us
$ (k-1)^{p(p-1)}\equiv 1 \pmod {p}$, and therefore 
$ k((k-1)^{p^2}-2(k-1)) \equiv k((k-1)^{p}-2(k-1))\equiv -k(k-1)   \pmod {p}$.
Since $p$ divides neither $k$ nor $k-1$, we arrive at the usual contradiction 
with (\ref{eq1}).

\item[{\rm (4)}] Since $p$ does not divide $k+2$, 
$ \frac{M(k,g)+4}{2}\equiv k+2 \not \equiv 0  \pmod {p}$ by Lemma~\ref{arithm}.
Since $p$ does not divide $k,k-1$, or $k-3$, we have
$ k((k-1)^{2p}-2(k-1)) \equiv k((k-1)^{2}-2k+2) \equiv k(k-1)(k-3) \not \equiv 0  \pmod {p}.$ 
The two congruencies together yield a contradiction with (\ref{eq1}).

\item[{\rm (5)}] The congruence $ k \equiv 3  \pmod{g}$ implies
$(k-1)^{g/2}-2k+2 \equiv 2^{g/2}-4  \pmod {g}$, while Lemma~\ref{arithm} yields 
$ \frac{(M(k,g)+4)k}{2} \equiv \frac{3(2\cdot2^{g/2}+2)}{2} \pmod {g} $.
Hence, 
\begin{align*} 
\frac{(M(k,g)+4)k}{2}((k-1)^{g/2}-2k+2) 
&\equiv \frac{3(2\cdot2^{g/2}+2)}{2}(2^{g/2}-4)\\ 
&\equiv 3(2^{g/2}+1)(2^{g/2}-4)  \pmod {g}. 
\end{align*}
Using $g\equiv0 \pmod {16}$ gives us $ \frac{g}{2} \geq 8 $, and therefore 
$ 2^{g/2} $, $ 2^{g/2+2} $, and $ 2^g $ are all congruent to $0$ modulo $16$, which 
implies $ \frac{(M(k,g)+4)k}{2}((k-1)^{g/2}-2k+2) \equiv 4  \pmod{16} $, i.e., 
$ \frac{(M(k,g)+4)k}{2}((k-1)^{g/2}-2k+2) $ is not congruent to $0$ modulo $g$, 
and we obtain a contradiction with (\ref{eq1}).
\end{itemize}
This completes the proofs.
\end{proof}

The non-existence of $(k,g)$-graphs of excess $4$ with parameters satisfying
the conditions of the above theorem does not immediately imply that the excess
of a $(k,g)$-cage must be larger than $4$. Nevertheless, combining the above
result with the previously known restrictions does imply such conclusion for 
all of the above parameter pairs. Specifically, as noted in the introduction,
there are no Moore graphs of girth $10$ or girth greater than $12$. Furthermore,
Theorem~\ref{bigito} claims the non-existence of even girth graphs of excess
$1$ and degree $k \geq 3$ as well as excess $3$ and degree $k \geq 5$. 
Finally, Theorem~\ref{excess2}, excludes the possibility of even girth graphs
of girth greater than $6$ and excess $2$. These results, combined with
Theorem~\ref{exclude} yield the following.

\begin{corollary} Let $(k,g)$ be one of the pairs of parameters listed 
in Theorem~\ref{exclude}. Then, 
$ n(k,g) \geq M(k,g) + 5 $, for $k$ even, and $ n(k,g) \geq M(k,g) + 6 $,
for $ k $ odd.
\end{corollary}
\begin{proof}
We have proved the corollary prior to its statement for all $ g > 12 $. 
The only pair $(k,g)$ covered by Theorem~\ref{exclude} that cannot be 
excluded based on the above arguments is the pair $(3,10)$. 
However, $ n(3,10)$ is known to be equal to $70$ (see e.g. \cite{exojaj}),
while $ M(3,10) = 62$.
Hence, the claim is true for the pair $(3,10)$ as well.
The case of odd $k$
follows from the fact that the Moore bound for even $g$ is even, and the
order of a $k$-regular graph with odd $k$ must be even.
\end{proof}

\section{Graphs of even girth and excess larger than $4$}

It has been observed in \cite{BagFil&Jaj} that in case of odd degree, even girth, and excess $2$, all subgraphs induced by edge excess vertices are isomorphic to $K_2$. 
In the previous section, 
we have proved  that in case of even girth greater than $6$
and excess $4$, all
subgraphs induced by the edge excess sets must be isomorphic to 
$ 2K_2$.  If one was willing to see a pattern in these observations,
one might be tempted to try to prove that the edge excess set 
induced subgraphs of graphs with small excess and large even girth must always be isomorphic to $tK_2$, for some $ t \geq 1 $. 
Graphs of such structure play a prominent role in \cite{bigito} and 
are in a way the extreme $(k,g)$-graphs with odd 
$k$ and even $g$ and
the property that each subgraph $X_f$ induced by the $e=2t$ excess vertices
associated with an edge $f$ contains the minimum necessary number of 
edges, namely $t$ edges.
These are also the graphs that maximize the number of girth cycles through any
edge of the graph.
In this last section of our paper, we prove that for any arbitrarily large excess $e$
there exist parameters $k$ and $g$ with the property that the excess of 
all $(k,g)$-graphs from our restricted family exceeds~$e$.


\begin{lemma}\label{last-count}
Let $ k \geq 6 $, $ g = 2m \geq 6 $, and let $G$ be a $(k,g)$-graph
of even excess $e = 2t \leq k-2 $. If $ f $ is an edge of $G$ with excess
set $X_f$ of size $2t$ and the subgraph induced by $X_f$ in $G$ consists 
of $t$ copies of $K_2$, then 
\[ \overline{\bf c}_G(f,g) = (k-1)^m - t(k-1). \]
\end{lemma}
\begin{proof}
The proof is almost identical to that of Lemma~\ref{4count}, Part 1.
\end{proof}

\begin{theorem}\label{last}
For every $ e \geq 1 $, there exist parameters $ k,g $, $k$ odd, 
$g$ even, 
such that if $G$ is a $(k,g)$-graph satisfying the property that for
every edge $f$ of $G$ the subgraph induced by $X_f$ in $G$ is
isomorphic to disjoint copies of $K_2$'s, then $G$ has excess larger than $e$.
\end{theorem}
\begin{proof}
Let $m$ be a prime larger than
$e$, and also large enough to admit the existence of an odd $k$ such that $ e+2 < k < m $
and $ k \equiv 5 $ or $ 7 \pmod{8} $. Take $g=2m$, 
and assume that $G$ is a $(k,g)$-graph satisfying the property from our theorem. 
We claim that the excess of $G$ must be larger than $e$. To see this, assume to the 
contrary that the excess of $G$ is $ e' \leq e $. Then $ e' < k-2 $, and Theorem~\ref{bigito}
asserts that $G$ is bipartite, in which case we know that $e'=2t'$, for some integer $t'$.
Employing Lemma~\ref{last-count} yields $ \overline{\bf c}_G(f,g) = (k-1)^m - t'(k-1) $, for
all edges $f \in E(G) $, and therefore $g$ divides 
$ \frac{(M(k,g)+e') \cdot k}{2} \cdot ((k-1)^m - t'(k-1)) $.
Since $ M(k,g)= 2 \frac{(k-1)^m-1}{k-2} $, the girth $ g=2m $ of $G$,
and therefore also the prime $m$, divide 
the product 
\[ \frac{(2\frac{(k-1)^m-1}{k-2}+e') \cdot k}{2} \cdot ((k-1)^m - t'(k-1)). \] 
We claim, however, 
that neither of the two factors of this product is divisible by $m$.
We prove our claim separately for each of the factors.
Since $m$ is a prime, it follows from 
Fermat's Little Theorem that $(k-1)^m \equiv k-1 \pmod{m}$, and therefore 
\[  \frac{(2\frac{(k-1)^m-1}{k-2}+e') \cdot k}{2} \equiv \frac{(2 + e')}{2} \cdot k 
 \pmod{m}. \] 
Since $ 2 \leq e' + 2 \leq e + 2 < k < m $, $ \frac{(2 + e')}{2} \equiv (1+t')  \not \equiv 0 \pmod{m} $.
Similarly, the choice $ e+2 < k < m $ yields $ k \not \equiv 0 \pmod{m} $, and thus
neither $m$ nor $g$ divide the first of the factors.
Employing Fermat's Little Theorem again,
$ (k-1)^m - t'(k-1) \equiv (k-1) \cdot (1-t') \pmod{m} $. Note that our choice of 
$ k \equiv 5 $ or $ 7 \pmod{8} $ allows us to use Theorem~\ref{excess2} and conclude
that $ e' \neq 2 $, hence $ t' \neq 1 $, and $ (1-t') \not \equiv 0 \pmod{m} $.
As $k-1$ is also not divisible by $m$, the factor $ (k-1)^m - t'(k-1) $
is not divisible by $m$ either.
Since none of the factors is congruent to $0$ modulo $m$, the product  
$ (M(k,g)+e') \cdot \frac{k}{2} \cdot ((k-1)^m - t'(k-1)) $ is not divisible by $g$, and we obtain a
contradiction. The excess of $G$ is therefore bigger than~$e$.
\end{proof}

If one were able to prove that (a sufficient portion) of the 
$(k,g)$-graphs whose parameters satisfy the conditions stated at the 
beginning of the proof of Theorem~\ref{last} {\em must} have the structure
described in the statement of the theorem, the above result would yield that for
each excess $e>0$, there exist parameters $(k,g)$ with the property that the excess of any $(k,g)$-graph $G$ exceeds $e$. The existence of such
parameter pairs for arbitrarily large $e$ has already been established 
for the (much more restricted) 
family of vertex-transitive $(k,g)$-graphs \cite{Big,Fil&Jaj}, but has only 
been conjectured for the case of general cages. Using as further evidence
the excess of the best known $(k,g)$-graphs listed in the tables of \cite{exojaj}, 
the existence of $(k,g)$-cages of arbitrarily large excess feels like a foregone 
conclusion. Nevertheless, any such proof has been elusive so far, and the
conjecture, though widely believed, stays frustratingly unproved.
\begin{thebibliography}{10}

\bibitem{Big}
N.\ L.\ Biggs. \newblock Excess in vertex-transitive graphs. \newblock Bull. London Math. Society 14 (1982) 52-54.

\bibitem{banito}
E.\ Bannai and T.\ Ito. \newblock
On finite Moore graphs. \newblock
J. Fac. Sci. Tokyo, Sect. 1A, 20 (1973) 191-208.

\bibitem{Ban&Ito}
E.\ Bannai and T.\ Ito. \newblock
Regular graphs with excess one. \newblock
Discrete Math. 37 (1981) 147-158.

\bibitem{bigito}
N.\ L.\ Biggs and T.\ Ito. \newblock
Graphs with even girth and small excess. \newblock
Math. Proc. Camb. Philos. Soc. 88 (1980) 1-10.

\bibitem{dam}
R.\ M.\ Damerell. \newblock
On Moore graphs. \newblock
Proc. Cambridge Phil. Soc. 74 (1973) 227-236.

\bibitem{erdossachs}
P.\ Erd\H{o}s and H.\ Sachs. \newblock
Regul\" are Graphen gegebener Taillenweite mit minimaler Knotenzahl. \newblock
Wiss. Z. Uni. Halle (Math. Nat.) 12 (1963) 251-257.

\bibitem{erosch}
L.\ Eroh and A.\ Schwenk. \newblock
Cages of girth 5 and 7. \newblock
Congr. Numer. 138 (1999) 157-173.

\bibitem{exojaj}
G.\ Exoo and R.\ Jajcay. \newblock
Dynamic cage survey. \newblock
Electron. J. Combin., Dynamic Survey 16, September 2008.

\bibitem{Fil&Jaj}
S.\ Filipovski and R.\ Jajcay. \newblock
On the excess of vertex-transitive graphs of given degree and girth. \newblock
Submitted for publication.

\bibitem{fri}
H.\ D.\ Friedman. \newblock
On the impossibility of certain Moore graphs. \newblock
J. Comb. Theory 10 (1971) 245-252.

\bibitem{garbe}
F.\ Garbe. \newblock
On graphs with excess or defect $2$. \newblock
Discrete App. Math. 180 (2015) 81-88.

\bibitem{jajsir}
R.\ Jajcay and J.\ \v Sir\' a\v n. \newblock
Small vertex-transitive graphs of given degree and girth. \newblock
Ars Mathematica Contemporanea 4 (2011) 375-384.

\bibitem{BagFil&Jaj}
T.\ B.\ Jajcayov\' a, S.\ Filipovski and R.\ Jajcay. \newblock
Counting cycles in graphs with small excess. \newblock
Accepted for publication in Lecture Notes of Seminario Interdisciplinare di
Matematica.

\bibitem{kovacs}
P.\ Kov\' acs.  \newblock 
The non-existence of certain regular graphs of girth 5.  \newblock
J. Combin. Theory Ser. B 30 (1981) 282-284.

\bibitem{sachs}
H.\ Sachs.  \newblock
Regular graphs with given girth and restricted circuits.  \newblock
J. London Math. Soc. 38 (1963) 423-429.

\end{thebibliography}
\end{document}


\begin{lemma} \label{no-moore-cycles}
Let $G$ be $(k,g)$-graph of {\em odd girth} $g$ and $|V(G)| = M(k,g) + N $, for some $ 0 < N $.
Then the following inequalities hold for all $ v \in V(G) $:
\[ \frac{k}{2} (k-1)^{(g-1)/2} -N \cdot k \leq {\bf c}_G(v,g) \leq \frac{k}{2} (k-1)^{(g-1)/2} - N. \]
\end{lemma}
\begin{proof}
One of the key observations of this proof, is the fact that the sets $N_i(v)$ for $ 0 \leq
i \leq (g-1)/2 $ are exactly the same as those in the proof of Lemma~\ref{moore-cycles};
including the fact that none of the layers $N_i(v)$ for $ 0 \leq i < (g-1)/2 $ contains horizontal
edges. The main difference as compared to the previous proof is the existence of at least
one additional layer $N_i(v)$ with $(g-1)/2 < i$.
Consider cycles of length $g$ through a fixed vertex $v \in V(G)$. As before,
every such cycle consists of two paths of length
$(g-1)/2$ connecting $v$ to two vertices $u_1,u_2 \in N_{(g-1)/2}(v)$ and one horizontal
edge connecting $u_1$ to $u_2$ (the existence of $N_i(v)$ with $(g-1)/2 < i$ has no impact
on the form of these cycles: one cannot visit these layers without departing too far from $v$).
Thus, as before, the number ${\bf c}_G(v,g)$ is equal to the number of horizontal edges
connecting vertices from $N_{(g-1)/2}(v)$. Since $N$ is assumed to be greater than $0$,
and each vertex $w \in N_{(g+1)/2}(v) $ must be connected to some vertex in
$ N_{(g+1)/2}(v) $, the number of horizontal edges in $N_{(g-1)/2}(v)$ is at most
\[ |N_{(g-1)/2}(v)| \cdot \frac{(k-1)}{2} - N = \frac{k}{2} (k-1)^{(g-1)/2} -N. \]
On the other hand, the set of vertices whose distance from $v$ is larger than $(g-1)/2$ is
$N$, and thus there are at most $N \cdot k$ edges connecting the vertices in
$ N_{(g-1)/2}(v) $ to the vertices in $ N_{(g+1)/2}(v) $. It follows that the number of
horizontal edges between the vertices in $ N_{(g-1)/2}(v) $ is bounded from below by
\[ |N_{(g-1)/2}(v)| \cdot \frac{(k-1)}{2} - N \cdot k = \frac{k}{2} (k-1)^{(g-1)/2} -N \cdot k, \]
and the bounds on ${\bf c}_G(v,g)$ follow.
\end{proof}

We note in conclusion of this section that similar bounds to those in
Lemma~\ref{no-moore-cycles} for the numbers ${\bf c}_G(v,g+1)$ and
${\bf c}_G(v,g+2)$ appear feasible. However, the analysis is just a bit more complex than
the above, and so we choose not to develop such bounds. The results of
Lemma~\ref{no-moore-cycles} will suffice for proving the improved lower bounds on the
order of cages.


The combinations of Lemmas \ref{cycles} and \ref{no-moore-cycles} yields the
following key observation of this section:
\begin{lemma}\label{key}
Let $G$ be $(k,g)$-graph of {\em odd girth} $g$ and $|V(G)| = M(k,g) + N $, for some $ 0 < N $.
Then the interval
\[ (M(k,g)+N) \cdot (\frac{k}{2} (k-1)^{(g-1)/2} -N \cdot k), (M(k,g)+N) \dot
(\frac{k}{2} (k-1)^{(g-1)/2} - N) \]
must contain a number divisible by $g$.
\end{lemma}
\begin{proof}
The result follows from the two inequalities
\[ (M(k,g)+N) \cdot (\frac{k}{2} (k-1)^{(g-1)/2} -N\cdot k) \leq \sum_{v \in V(G)} {\bf c}_G(v,g)
\leq (M(k,g)+N) \dot
(\frac{k}{2} (k-1)^{(g-1)/2} - N) \]
that follow from Lemma~\ref{no-moore-cycles} and from Lemma~\ref{cycles}.
\end{proof}

The proof of the second divisibility claim follows the usual lines of argument. 
Cycles of length $(g+2)$ rooted at some $ u \in V(G) $ come in at most three ways 
(regardless of the type of $u$). Either they include no vertices from $X_u$, and hence 
include a path consisting of three consecutive horizontal edges; or they contain one
vertex from $X_u$, in which case they include a $3$-path consisting of a 
leaf-to-excess-vertex edge followed by an excess-vertex-to-leaf edge and a horizontal edge incident with the second leaf; or they contain both excess edges and therefore contain
a leaf-to-excess-vertex edge followed by an edge connecting the two excess vertices and
finally followed by an excess-vertex-to-leaf edge (this case impossible for
vertices of type $d2$ or $d3$ which do not allow for edges between their corresponding 
excess vertices).
The key to correct counting of these three types of cycles for different types of vertices
$u$ lies in correctly determining the numbers of consecutive triples of horizontal edges,
and determining the `horizontal' degrees of the leaves. Each of the three types $d1,d2,d3$
yields a slightly different result as listed in the claim of our lemma. The actual details are
left to the reader. 




\begin{lemma}\label{unique}
Let $ k \geq 7 $ be odd, $ g = 2m \geq 8 $. Let $G$ be a $(k,g)$-graph
of excess $4$. Then all edges of $G$ must be of type $2K_2$ and all vertices of $G$
must be of the first $2K_2$ type.
\end{lemma}
\begin{proof}
Assume that $ k \geq 7 $ is odd, $ g = 2m \geq 8 $, and $G$ is a $(k,g)$-graph
of excess $4$. Let $u$ be an arbitrary vertex of $G$. Since every $g$-cycle through $u$
contains $2$ edges incident with $u$, the sum of the numbers $ \overline{\bf c}_G(f,g) $ through all
$f$ incident with $u$ must be even. Note that the choice of odd $k$ together with 
Lemma~\ref{4count} yield that 
$ \overline{\bf c}_G(f,g) $ is even when $X_f$ gives $2K_2$ and is odd otherwise. Since the 
sum of the $ \overline{\bf c}_G(f,g) $'s at $u$ must be even, it follows that not all the numbers 
$ \overline{\bf c}_G(f,g) $ can be odd. Consequently, if $k$ is odd, each vertex $u$ of $G$ 
must be incident with at least one edge of type $2K_2$. As noted above, this means that no
vertex $u$ in $G$ can be of the second $2K_2$ type as that would force two different numbers of
$g$-cycles through $u$. Suppose finally that $u$ is both of the first $2K_2$ type and 

The following theorem immediately follows.

\begin{theorem}\label{exc2}
Let $ k \geq 6 $, $ g = 2m \geq 6 $, and let $G$ be a $(k,g)$-graph
of excess $4$.
Let $x_1$ be the number of edges for which $ G[w_1,w_2,w_3,w_4] $ is isomorphic to $2K_2$, and $x_2$ be the number of edges for which
$ G[w_1,w_2,w_3,w_4] $ is isomorphic to ${\mathcal P}_3$. 
Then the following must be satisfied:
\begin{enumerate}
\item $ x_1 + x_2 = (M(k,g)+4) \cdot \frac{k}{2} $;
\item $ g \; | \; x_1 \cdot [(k-1)^m - 2k +2] + x_2 \cdot 
[(k-1)^m - 2k + 3] $.
\end{enumerate}

In particular, if no non-negative integers $ x_1,x_2 $ satisfying the above arithmetic
conditions exist, no $(k,g)$-graphs of excess $4$ exist.
\end{theorem}


