<p>6-regular Ramanujan graphs have girth (shortest cycle length) <span class="math-container">$\Omega(\log n)$</span>, 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 <span class="math-container">$\Omega(n^c)$</span> for some <span class="math-container">$c$</span> with <span class="math-container">$0&lt;c&lt;1$</span>. Turning this ratio around, if <span class="math-container">$k$</span> is the size of the smallest 3-regular subgraph in a 6-regular Ramanujan graph, the overall graph has size <span class="math-container">$O(k^{1/c})$</span>, a polynomial.</p>

CC BY-SA 4.0
2023-05-04T07:10:17.553Z
That's not what I get when I plug in the girth of 6-regular LPS Ramanujan graphs into the Moore bound for 3-regular graphs.
David Eppstein
CC BY-SA 4.0
2023-05-08T05:07:52.503Z
(Comment was in reply to a suggestion for what c is)
David Eppstein
CC BY-SA 4.0
2023-05-03T19:30:16.430Z
2023-05-03T19:30:16.430Z
David Eppstein
<p>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 <span class="math-container">$poly(k)$</span> that does not have any 3-regular subgraphs of size <span class="math-container">$k$</span> or less (<span class="math-container">$k$</span> is some positive integer).</p>
<p>I have thought of a cycle of size <span class="math-container">$poly(n)$</span> 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). <br></p>
<p>I have also considered having three sets of vertices, each of size <span class="math-container">$k^2$</span> and the adjacency is carefully defined between the sets such that no 3-regular subgraph of size at most <span class="math-container">$k$</span> is present. But, i can't quite prove it formally whether my graph does not have a 3-regular subgraph of size at most <span class="math-container">$k$</span>.</p>
<p>Recently, I got to know about <span class="math-container">$(r,g)$</span>-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?</p>

CC BY-SA 4.0
2023-05-03T17:26:56.863Z
This paper is relevant: https://www.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
<graph-algorithms><polynomial-time>
6-regular graph without small 3-regular subgraph
Balchandar Reddy
# 6-regular graph without small 3-regular subgraph

(Asked by: username_0 on 2023-05-03)

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?

**Tags:** graph-algorithms, polynomial-time
> **Comments:**
> **username_1**: This paper is relevant: https://www.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.  

---

## 1 answers

### Answer by username_2 on 2023-05-03. Score: 8 | Accepted answer

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.

> **Comments:**
> **username_2**: That's not what I get when I plug in the girth of 6-regular LPS Ramanujan graphs into the Moore bound for 3-regular graphs.  
> **username_2**: (Comment was in reply to a suggestion for what c is)  

---

