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!

4more comments