I’ve just uploaded a paper “Quartic graphs with every edge in a triangle” to the arxiv — joint with Florian Pfender — that characterises the quartic graphs with the property that every edge lies in a triangle.
Although this property doesn’t seem all that strong at first sight, it is actually very restrictive when the graph is regular of low enough degree. We end up with an exact characterisation saying that a 4-regular graph with every edge in a triangle is either:
- a squared n-cycle, or
- the line graph of a cubic (multi) graph, or
- obtained from these by replacing triangles by copies of .
Exact structural characterisations of natural classes of graphs are appealing, and this contains a nice mixture of a thin infinite family, a general construction and an operation under which the class is closed.
While I was working on a problem (that I have still not solved) to do with a certain minor-closed class of graphs, I wanted to know the -regular graphs where every edge lies in a triangle. Now triangles are such a fundamental graph-theory concept, and there are so many results about graphs that are in some sense extremal with respect to their triangle structure, that I was convinced that someone must have said something useful about these graphs. But after searching MathSciNet and Google Scholar without success, I decided to have a look at the small cases by computer, starting with 4-regular graphs (3-regular being trivial).
Shortly afterwards, I had the following numbers of connected 4-regular graphs with every edge in a triangle: 1, 1, 2, 2, 3, 3, 4, 8, 11, 18, 35, 57 and 106 for 5-17 vertices respectively.
Small numbers that grow slowly is the ideal outcome for this sort of experiment, strongly suggesting a few controllable families of graphs, rather than an uncontrollable mess. So then I went to MathOverflow primarily to find out if anyone had seen anything similar (http://mathoverflow.net/questions/84783/4-regular-graphs-with-every-edge-in-a-triangle).
But I got something much better.
Florian Pfender, who I had met 10 years ago in Berlin, but who is now in Colorado, picked out a couple of families, and after I confirmed that these seemed to cover all the examples, sketched out a rough argument about why this should be the case.
We joined forces, and after a few iterations involving filling some holes, ensuring the small cases were included properly, refining the argument and extending it to multigraphs, we ended up with this paper.
So what about 5-regular graphs, which was the very original problem? Well, here the numbers are much less appealing: 1, 3, 24, 308, 4921, 98829 graphs for 6, 8, 10, 12, 14 and 16 vertices respectively!
I’m tempted to just say that this is an uncontrollable mess, but perhaps someone can figure out what to do.