\documentclass[12pt]{article} \usepackage{e-jc} \usepackage{amsthm,amsmath,amssymb} \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{ 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{submission date}{acceptance date}\\ % \small Mathematics Subject Classifications: comma separated list of % MSC codes available from http://www.ams.org/mathscinet/freeTools.html} \date{\dateline{Jan 1, 2012}{Jan 2, 2012}\\ \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) + ... + k(k-1)^{(g-3)/2}, & g \mbox{ odd, } \\ 2 \left( 1 + (k-1) + ... + (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 \[ {\bf c}_G(u,g) = \] \[ ((k-1)^m - 2k +2) + ((k-1)^{m-1}-2k+3) \cdot {k-1 \choose 2} + (2k-4){k-2 \choose 2} + {k-3 \choose 2} + 2 {k-1 \choose 2} ,\] 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$: \[ {\bf c}_G(u,g) = \] \[ ((k-1)^m - 2k +3) + ((k-1)^{m-1}-2k+3) \cdot {k-1 \choose 2} + (2k-3){k-2 \choose 2} + {k-2 \choose 2} + {k-1 \choose 2} . \] \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{description} \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{description} 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{eqnarray*} \frac{(M(k,g)+4)k}{2}((k-1)^{g/2}-2k+2) \equiv \\ \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{eqnarray*} 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}