I am interested in regular graphs in which every edge lies in a triangle.


For 3-regular graphs, only the complete graph $K\_4$ has this property, so there's not much to see here.


For 4-regular graphs, there are more graphs, including some infinite families, but few enough and slowly-growing enough that I have some wild hope of a characterisation. 


The numbers on 5, 6, ..., 17 vertices are


1, 1, 2, 2, 3, 3, 4, 8, 11, 18, 35, 57 and 106,


which is tiny compared to the total number of 4-regular graphs.


For smaller numbers of vertices there are likely to be numbers of graphs that "just happen" to have every edge in a triangle, but at some stage I am hoping they will fall into some infinite families for which one might get at least a qualitative description.


I have searched "the literature" (i.e. tried MathSciNet and Google) and cannot find any results along these lines which surprised me a bit. But perhaps it is just impossible and those numbers just keep growing...


So my question is:


Does anyone know any results or have any ideas pertaining to regular graphs, in particular 4-regular graphs, with every edge lying in a triangle?


EDIT: I think that Florian Pfender (see comment below) may have basically found the solution. All of the graphs that I have computed (on up to 17 vertices) are either:


(a) The Cayley graph Cay$(Z\_n; \{ \pm 1,
 \pm 2 \})$ ("the square of a cycle")


(b) The linegraph of a cubic graph, or


(c) have an edge $xy$ such that the closed neighbourhood of $x$ is equal to the closed neighbourhood of $y$


This latter condition means that the two vertices $x$, $y$ have exactly three common neighbours, say $a$, $b$ and $c$. So we can reduce to a smaller graph by deleting $x$ and $y$ and adding a triangle on $a$, $b$, $c$ perhaps at the expense of introducing multiple edges.


Last thing that remains is to show that when this "reduction process" is completed, the resulting graph is just the line-multigraph of a cubic-multigraph, which is what Florian implied.


I am hopeful of a genuine result here.


(Then on to 5-regular graphs....)


FINAL EDIT: August 2013 - This question has now generated a paper containing the genuine result that I was hopeful for. See <http://arxiv.org/abs/1308.0081> and <https://symomega.wordpress.com/2013/08/02/regular-graphs-triangles-and-mathoverflow/>.


Thanks MathOverflow!



4-regular graphs with every edge in a triangle
yes, it feels like one could proof my characterization along the following lines:


* If the graph does not contain $K\_4^-$, then it is a line graph of a 3-regular graph.
* Now continue with a copy of $K\_4^-$. The two vertices of degree three must each be incident to another edge. If these two edges meet, then we can reduce the whole structure to a triangle like you describe (my $K\_{3,1,1}$).
* If the two edges do not meet, then they each must lie in a triangle, so there need to be edges from their endpoints to the vertices of degree 2 in the $K\_4^-$. If both these edges meet in the same vertex, we again have a structure we can reduce to a triangle (a triangle in the line graph original, which we can contract keeping 3-regularity).
* So we are left with the case where the two edges go to different sides of the $K\_4^-$, and again we have two vertices of degree 3 to work with. If these two vertices are connected, then we have a $K\_4$ with two triangles attached to it which we can get from the multi-line-graph of edge-doubleedge-edge by $K\_{3,1,1}$ing one of the triangles (or alternatively, we can reduce the whole graph by contracting the whole structure to one vertex).
* If these two vertices are not connected, then each must lie in a triangle with the neighboring vertex of degree 2, and this process will go on until the two sides meet in a cycle, in which case you got your square of a cycle.


