\section{Declarations}
\begin{itemize}
\item
Funding: Cape Breton University RISE grant 80306
\item
Conflicts of interest/Competing interests: None
\item
Availability of data and material: N/A
\item
Code availability: N/A
\item
Authors' contributions: All the sole author's work 
\end{itemize}

\section{Introduction}\label{s:intro}

For other basic graph theory definitions, please see \cite{bo:rd}. In this paper a triangle in a graph will be defined as a set of three distinct vertices with an edge between each pair of vertices. 
We are interested in graphs such that every edge is in at least one triangle, we refer to this as {\em the triangle property}. 
In particular, we are looking for graphs which have the fewest triangles in them with regards their regularity and number of vertices while still having the triangle property; such graphs we will call {\em optimal}. 
By our definition of a triangle multiple edges are permitted in graphs with the triangle property but loops cannot be in a triangle since they must repeat a vertex. Any triangle that contains a multiple edge will lead to multiple triangles using those same three vertices.

The same fundamental lemma from \cite{ar:PR} which characterises all 4-regular graphs with the triangle property is also still true for any regular graph:

\begin{lem}\label{l:triv} \cite{ar:PR}
A graph $G$ has the triangle property if and only if, for every vertex $v \in V (G)$,
the graph induced by the neighbourhood of $v$ contains no isolated vertices.
\end{lem}

For 2-regular and 3-regular graphs with the triangle property the only graphs are disjoint copies of complete graphs, $y K_3$ and $z K_4$, respectively, for any positive integers $y$ and $z$, so there is nothing more to say about them. However, one consequence of lemma \ref{l:triv} is the following lower bound for the number of triangles in an optimal graph with even regularity:

\begin{thm}\label{t:eventri}
If $r$ is an even positive integer and $G$ is a graph with $n$ vertices  which is $r$-regular and has the triangle property, then there are at least $\frac{nr}{6}$ triangles. In the optimal case these triangles are also arranged in a distinctive pattern.
\end{thm}

\begin{proof}
Let $G$ be an $r$-regular graph with $n$ vertices which has every edge in a triangle, and let $r:=2s$ for any non-negative integer $s$.
By lemma \ref{l:triv} the $2s$ neighbours of any vertex in $G$ must induce a graph with no isolated vertices, and the graph satisfying this with fewest edges is $sK_2$ which has $s$ edges. Since each edge in the induced neighbourhood produces a triangle in $G$ there are at least $s$ triangles at any vertex. Thus, when we count the triangles at every vertex, and each triangle is counted three times, the number of triangles in $G$ is at least $\frac{ns}{3}=\frac{nr}{6}$.

Now suppose that $J$ is a optimal $2s$-regular graph with $n$ vertices and $ns$ edges which are all in exactly one of the $\frac{ns}{3}$ triangles in $J$. By the above we can see that there are exactly $s$ triangles at each vertex and now we can form a new graph $H$ from $J$ by creating a vertex for each triangle and adding an edge between any two vertices in $H$ if their triangles in $J$ shared a vertex.

Since each vertex in $H$ corresponds to a triangle in $J$ and at each vertex in $J$ there are $s$ triangles, there are $3(s-1)$ triangles in $H$ which share a vertex with every triangle. $H$ is therefore a $3(s-1)$-regular graph and each vertex in $H$ is incident with $3$ copies of $K_s$.\qed
\end{proof}

Immediately we can see this confirms what we said about 2-regular graphs; when $r=2$ we need $H$ to be a 0-regular graph and so must be copies of $K_1$. Replacing each vertex in $H$ by a triangle we get a number of copies of $K_3$ as expected. 

\begin{cor}
Optimal 4-regular graphs are line graphs of 3-regular triangle-free graphs.
\end{cor}

\begin{proof}
If $s=2$ and $J$ is a minimal 4-regular graph with every edge in a triangle then, by Theorem \ref{t:eventri}, $H$ corresponds to the line graph of a 3-regular graph, one of the base families of graphs with the triangle property in \cite{ar:PR}. However, we need to ensure that $H$ is triangle-free, as otherwise, any triangle in $J$ will also appear in $H$ as a triangle too, and will not come from the three edges incident at a vertex in $H$.\qed
\end{proof}

It is also possible to create an optimal 6-regular graph from a 4-regular one and in general any optimal even regular graph if we start with a suitably large 4-regular graph and sequentially add triangles between the vertices of the previous optimal graph without creating any triangles with the existing graph edges. 

For instance, as shown in figure \ref{f:pete}, in the Petersen graph there are five sets of three edges which have two edges between them. If we take the line graph there are then five sets of three vertices distance 3 apart from each other. One set of three is shown in the figure, the other sets are rotations of these, and together they can be used to make five new triangles which can be added to the line graph to create a 6-regular graph with $\frac{nr}{6}=\frac{15 \times 6}{6} = 15$ triangles.


\begin{figure}[h]
\begin{center}
\includegraphics[width=0.9\textwidth]{peteandlineplus.png}
\end{center}
\caption{Edges in Petersen at distance 3 giving a 6 regular graph with 15 triangles}\label{f:pete}
\end{figure}


However, for 5-regular graphs, the situation is more complicated. The structure of the family of 5-regular graphs is investigated in an upcoming paper by the author
but the base graphs in that paper can contain multiple edges or copies of $K_4$ and do not have the minimal number of triangles.

\begin{thm}\label{c:triv}
In a 5-regular graph with $2n$ vertices which has the triangle property, there are at least $2n$ triangles and $n$ edges which are in two triangles or more.
\end{thm}

\begin{proof}
If $v$ is a vertex in a 5-regular graph $G$ with the triangle property then we can use Lemma \ref{l:triv}; if $v$ is adjacent to five distinct vertices in $G$ then the induced neighbourhood graph of $v$ has at least 3 edges, and hence a vertex $w$ of degree at least 2, which gives rise to at least two triangles containing the edge $vw$ in $G$. 
Similarly, if there is a multiple edge incident with $v$ then there must be at least one other edge $e$ incident with $v$ in a triangle and so $e$ is therefore in at least two triangles, using each edge of the multiple edge separately.

In addition to these triangles at $v$ they use at most three neighbours of $v$ and since the degree of $v$ is 5 there are two more vertices which haven't yet been included in a triangle, and must because $G$ has the triangle property, so there are at least three triangles at $v$. Counting the triangles at each vertex and dividing by the number of vertices in a triangle gives us at least $\frac{6n}{3} = 2n$ triangles in $G$.

Since at all $2n$ vertices there is at least one edge in two triangles or more, there are at least $n$ edges in $G$ which are in at least two triangles.
\qed
\end{proof}

\begin{remark}\label{r:odd}
We can argue similarly for $(2r+1)$-regular graphs with the triangle property for $r>2$. It will be necessary to have at least one vertex of degree 2 in the induced neighbourhood graph of every vertex, and so we have at least $(r+1)$ triangles incident with every vertex. Thus there must be at least $\frac{(r+1)n}{3}$ triangles in such a graph.
\end{remark}

\section{A family of optimal quintic graphs}

It turns out that, for $n\geq 7$, there do exist simple graphs that satisfy the inequality in Theorem \ref{c:triv}, such as by the following construction of a 5-regular or quintic graph $L_n$:
\begin{enumerate}[label=(\alph*)]
  \item Create $n$ vertices labelled 0 to $n-1$ with edges joined in a cycle 
\item 
For all $k$ from 0 to $n-1$, join vertex $k$ to a new vertex labelled $n+k$.
\item For $k$ from 0 to $n-1$ add an edge between vertex $n+k$  and
\begin{enumerate}[label=(\roman*)]
\item vertex $n+((k+2){\rm ~\!mod~} n)$.
 \item vertex $((k-2){\rm ~\!mod~} n)$ 
\item vertex $((k+1){\rm ~\!mod~} n)$.
\end{enumerate}
\end{enumerate}
$L_n$ is simple and 5-regular for $n\geq 5$; vertices 0 to $n-1$ are joined to two others in the cycle in (a) and one in (b) and two in (c), and the remaining $n$ vertices are joined to one vertex in (b) and four via (c). In $L_n$ the edges from vertex $k$ to vertex $n+k$, shown as the radial blue dashed spokes in figure \ref{f:l7} for $n=7$, are in exactly two triangles, with vertex $(k+1) {\rm ~\!mod~} n$ and vertex $n+ ((k+2){\rm ~\!mod~} n)$. The other two edges from vertex $k$ are to $(k-1){\rm ~\!mod~} n$ and $n+ ((k-1){\rm ~\!mod~} n)$ which also have an edge between them. Similarly, vertex $n+k$ is adjacent to vertices $(k-2){\rm ~\!mod~} n$ and $n+ ((k-2){\rm ~\!mod~} n)$ and so are part of that triangle. All of the different types of edges are in a triangle and so $L_n$ has the triangle property; there are only three triangles at vertices $k$ and $n+k$ and since $L_n$ is formed symmetrically, that is true for all vertices of $L_n$.

\begin{figure}[h]
\begin{center}
\includegraphics[width=0.5\textwidth]{L7.png}
\end{center}
\caption{The quintic graph $L_7$ which contains 14 vertices and 14 triangles}\label{f:l7}
\end{figure}

Note that this implies that $L_n$ contains exactly $2n$ triangles too, by counting the triangles at each vertex and dividing by the number of vertices in each triangle.
Additionally these triangles are arranged as $n$ edge-disjoint subgraphs isomorphic to the ${\rm diamond}$ ($K_{2,1,1}$ or $K_4^-$). This structure must hold for any simple 5-regular graph with $2n$ vertices and $2n$ triangles. In the remaining figures the edges that are in two triangles will again be coloured blue and dashed to highlight them.
If $n\leq 6$ then extra triangles are formed in $L_n$ using edges between vertices $n$ to $2n-1$, and for $n\leq 4$ multiple edges are created by this construction, so the graphs created are not optimal. $L_7$ is the graph with the fewest vertices which is optimal, as shown by an computer search using nauty \cite{ar:nauty}.

As in section \ref{s:intro}, examples of optimal odd-regular graphs can be constructed from an optimal 5-regular graph $F$ with $2n$ vertices by carefully adding triangles between triples of vertices of $F$ so as not to create any triangles other than those we are choosing to add. Note that this is only possible, by remark \ref{r:odd}, if $n$ is a multiple of 3 or $r$ is congruent to 2 mod 3.

For instance, if we take $L_{3j}$ for $j\geq 5$ and add edges between the triples of vertices between 0 and $3j-1$ that are congruent mod $j$, and then similarly join the vertices between $3j$ and $6j-1$ based on their congruence mod $j$, we will only create those $2j$ extra triangles, and so we have a family of optimal 7-regular graphs.

\section{Construction of all simple optimal quintic graphs}

\subsection{Diamonds and even cycle decompositions}
If we contract the $n$ blue dashed edges of $L_n$ between vertices $k$ and $n+k$ for $k$ from 0 to $n-1$ (the vertices of degree 3 in each ${\rm diamond}$ subgraph) then we get a 4-regular graph with $m$ vertices. We can trace even length cycles through these vertices corresponding to the arrangement of the ${\rm diamond}$s in $L_n$ since the degree 3 vertices in one ${\rm diamond}$ must be identified with the degree 2 vertices in another ${\rm diamond}$, and this continues on until the original ${\rm diamond}$ is repeated an even number of ${\rm diamond}$s later. This gives us an even cycle decomposition (as defined in \cite{ar:ecd}), but we will need a subset of these decompostions for our purposes:

If we list the cycles each starting with the same orientation of a ${\rm diamond}$ then each ${\rm diamond}$ will occur once in an even position in the sequence, the other in an odd one. For instance, in $L_7$, labelling the ${\rm diamond}$s cyclically from $a$ to $g$, we can get the following Eulerian cycle of the graph of ${\rm diamond}$s: $[a, c, b, d, c, e, d, f, e, g, f, a, g, b]$.

\begin{lem}\label{l:mint}
Optimal simple quintic graphs with $2n$ can all be formed from an even cycle decomposition of a 4-regular graph with $n$ vertices, by replacing the vertices by diamonds. The only restrictions for the even cycle decompositions are that it has these extra rules for any vertices $x$, $y$ and $z$ in the even cycle decomposition of the 4-regular graph:
\begin{enumerate}[label=(\roman*)]
\item
Either $[x,y]$ or $[y,x]$ can appear in cycles, not both, and only once.
\item
If $[x,y]$ and $[y,z]$ appear non-consecutively in cycles then $[z,x]$ cannot
\end{enumerate}
\end{lem}

\begin{proof}
As earlier, any optimal quintic graph $G$ must have one diamond and one triangle at each vertex. Since every vertex needs both and these are the only triangles in the graph, the vertices of degree 2 in the diamonds must be the triangles for other vertices. Thus, if $G$ has $2n$ vertices then there are $n$ diamonds joined together, comprising all $5n$ edges of $G$.

If we pick any diamond $D$ to start with and pick either diamond which is adjacent to it, we can traverse through the diamonds in the graph until we return in an even number of steps to $D$. If all diamonds are counted twice in this we are done, otherwise we repeat the process and get another even cycle of diamonds.

However, neither of the two cases specified in the lemma can occur without creating
additional triangles outside of the diamonds which cannot occur in an optimal graph as shown in figure \ref{f:moretri}.

\begin{figure}[ht]
\begin{center}
\includegraphics[width=0.8\textwidth]{dotsanddashes.png}
\end{center}
\caption{Dotted edges are also in more than one triangle}\label{f:moretri}
\end{figure}

In the left figure we have $[x,y]$ and $[y,x]$ appearing in our sequences and note that the dotted line is from both diamonds and therefore in two extra triangles with the blue dashed lines so the resulting graph is not optimal. Similarly, if $[x,y]$, $[y,z]$ and $[z,y]$ all appear then there is a triangle formed by edges of the diamonds which is not part of one of the original $n$ diamonds. Any larger cycles formed by the diamonds will not create any extra triangles, though.

Note that for $L_n$ we do get $[x,y,z,x]$ appearing as a cycle and no extra triangles are formed, but that isn't forbidden by the rules since they are consecutive diamonds. Additionally, within two cycles we cannot have $[x,y,z]$ and $[z,x]$ since $x$ and $z$ are the same parity in the former and the opposite parity in the latter, but each ${\rm diamond}$ must appear only twice, once in each parity.
\qed\end{proof}


\subsection{Multiple edges}

Lemma \ref{l:mint} also implies that each vertex in a simple optimal quintic graph must have the feature that all vertices are in exactly three triangles.
If a graph $G$ contains a vertex $v$ adjacent to a double edge $e$ then it is also possible for $v$ to be adjacent to three triangles, two triangles including either edge of $e$ and one other triangle to two other vertices.

Using this idea, one can try to create optimal quintic graphs with multiple edges at each vertex  by adding extra edges from a 1-factor of an optimal quartic graph to that graph as is done for the line graph of the cube in figure \ref{f:multopt}.

\begin{figure}[h]
\begin{center}
\includegraphics[width=0.5\textwidth]{optmult.png}
     \end{center}
\caption{A quintic graph with multiple edges with 12 vertices and 14 triangles}\label{f:multopt}  
\end{figure}

However, if the original 3-regular graph had $2n$ vertices, then its line graph will have $3n$ vertices and $2n$ triangles. Adding double edges according to the 1-factor will add $\frac{3n}{2}$ more triangles and
thus the 5-regular graph will have $2n + \frac{3n}{2} = \frac{7n}{2} > 3n$ triangles, so such a graph cannot be optimal.

It is not possible to have a mix of double edges along with the diamond arrangement, since then there will be a vertex which is not in a double edge, but is in a triangle $T$ with one. At each vertex like this there will be more than three triangles, two with $T$ and at least two more as in lemma \ref{l:triv} again.

\subsection{Removable edges}
One useful feature of any optimal simple 5-regular graph $G$ is that all edges $e$ in $G$ have the property that $G-e$ does not have every edge in a triangle. We shall call $e$ an {\em unremovable} edge and all other edges {\em removable}.

\begin{thm}\label{t:elig}
The only quintic graphs with the triangle property and with all edges as unremovable are the optimal graphs.
\end{thm}

\begin{proof}
Suppose $G$ is a quintic graph with the triangle property which has more triangles than vertices and all of the edges of $G$ are unremovable. $G$ cannot have a multiple edge since any edge that is part of a multiple edge is removable. Since there are more triangles than vertices there must be more than $m$ edges in $G$ which are in at least two triangles and hence there exist two such edges $e_1$ and $e_2$ which have a vertex $v$ in common. Because $G$ is simple and quintic and $e_1$ and $e_2$ are both in at least two triangles, at least two of the triangles at $v$ must have an edge in common. This edge is not $e_1$ or $e_2$ and it is also in at least two triangles.

\begin{enumerate}[label=\roman*)]
\item
Let us first suppose that $G$ does not contain a $K_4$.
Because $v$ has degree 5 we can now assume that $e_1$ and $e_2$ are two edges in two triangles which are also part of a triangle with each other, and, moreover, that the third edge of that triangle, $e_3$ is also in at least two triangles since otherwise it is removable, and we therefore have the symmetrical situation shown in figure \ref{f:blueadj}.

\begin{figure}[ht]
\begin{center}
\includegraphics[width=0.4\textwidth]{dashedtri.png}
\end{center}
\caption{No $K_4$ and adjacent edges in more than one triangle}\label{f:blueadj}
\end{figure}

 If $u_i = u_j$ (for some $i\not =j$), or $u_jv_j$ is an edge then we have $K_4$ as a subgraph, contrary to our supposition. We will thus assume that all 6 vertices are distinct and have no edges from any $v_j$ other than those shown in figure \ref{f:blueadj}.

All three vertices $v_1$, $v_2$ and $v_3$ in figure \ref{f:blueadj} need to be degree 5, and so need one more edge that must be in a triangle.
If all are adjacent to the same vertex then there is again a $K_4$, so we can assume that $v_3$, say, is adjacent to a vertex, $w_3$ that isn't a neighbour of $v_1$ and $v_2$ . There must be an edge from $w_3$ to either $u_1$ or $u_2$, and there is symmetry, so we can assume $w_3u_2$ is an edge, but that means that $v_3u_2$ is in two triangles. 
This now implies that $u_2v_1$ is in two triangles too, as otherwise it is removable.

We therefore must have, in $G$, a ${\rm diamond}$ which has all five edges which are in at least two triangles, and thus there must be four triangles each with an edge from the 4-cycle of the ${\rm diamond}$. Either a $K_4$ will be formed or the edge $f_1$ in figure \ref{f:bluedtri}will be removable unless it is part of a triangle which doesn't have any of these vertices in, as with vertex $y$.
However, in this case, the four triangles must all have blue edges if they are to be removable, but then edge $f_2$ will be removable.

\begin{figure}[ht]
\begin{center}
\includegraphics[width=0.4\textwidth]{megadiamond.png}
\end{center}
\caption{Many edges in more than one triangle}\label{f:bluedtri}
\end{figure}

\item
If there is a $K_4$ in $G$ then each edge of it is in two triangles in the $K_4$ alone. Moreover, each is removable unless it is part of another triangle. However, there are only two more edges to add, so at least one of the edges from each vertex in the $K_4$ is also in at least two triangles. This means that there must now be a subgraph which is isomorphic to $K_5 \backslash E(K_2)$, and all edges are necessarily in at least two triangles. Now, as before, each of these edges will be removable unless they are part of a triangle with a new vertex, which tells us that there must be a subgraph isomorphic to $K_6\backslash E(K_3)$. However, the edges between the vertices of degree 5 in this subgraph are removable.
\end{enumerate}
\qed
\end{proof}



