My name is Balchandar Reddy. I am a research scholar and am currently working on graph algorithms. I am looking to find a 6-regular graph that does not have small 3-regular subgraphs. For example, I want to generate a 6-regular graph of size $poly(k)$ that does not have any 3-regular subgraphs of size $k$ or less ($k$ is some positive integer).
I have thought of a cycle of size $poly(n)$ to start with, and I am yet to figure out the other type of adjacency between the vertices (as all the vertices need to have another four vertices adjacent to them to make the graph 6-regular).
I have also considered having three sets of vertices, each of size $k^2$ and the adjacency is carefully defined between the sets such that no 3-regular subgraph of size at most $k$ is present. But, i can't quite prove it formally whether my graph does not have a 3-regular subgraph of size at most $k$.
Recently, I got to know about $(r,g)$-cages that will construct such kinds of graphs without having smaller cycles. Can we modify it in some way such that it works for 3-regular subgraphs as well?