6-regular graph without small 3-regular subgraph

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?

• This paper is relevant: sciencedirect.com/science/article/pii/0095895684900479 It shows that every 6-regular graph has a 3-regular subgraph. I'm not sure how many nodes are in the subgraph they construct, but it will give you a starting bound on the relationship between the size of the input graph and the size of the 3-regular subgraph you want to forbid.
– GMB
May 3, 2023 at 17:26

6-regular Ramanujan graphs have girth (shortest cycle length) $$\Omega(\log n)$$, which means that their smallest 3-regular subgraphs do as well. However, the Moore bound on cages implies that every 3-regular subgraph has size at least exponential in its girth, which is therefore of the form $$\Omega(n^c)$$ for some $$c$$ with $$0. Turning this ratio around, if $$k$$ is the size of the smallest 3-regular subgraph in a 6-regular Ramanujan graph, the overall graph has size $$O(k^{1/c})$$, a polynomial.