<p>Let $G$ be an $n$-node graph that can be decomposed into two disjoint union of spanning trees.  In particular, $G$ has $2n-2$ edges. </p>

<p>It is not hard to show that the girth of $G$ is at most $O(\log n)$.  However, I don't have an example with girth bigger than $4$.  </p>

<blockquote>
  <p>Do we have an example of such graph whose girth is $\Theta(\log n)$, or is there a way to prove an even better upper bound?</p>
</blockquote>

<p>I wonder if there are constant degree expanders that, after removing an appropriate number of edges, can be decomposed into two disjoint union of spanning trees.</p>

CC BY-SA 3.0
2017-10-25T22:23:18.037Z
Not sure if this can be generalized, but here is a graph on $\mathbb{Z}/2n\mathbb{Z}$ with girth $6$, where $(x,y)\in E$ iff $x-y$ has the following values: $\pm 1$, or $\pm 2p$ when $x$ is even, or $\pm 2q$ when $x$ is odd. Here $p,q,n$ are coprime and $1<p<q-1$. The graph can be decomposed into two Hamiltonian paths with two extra edges.
Wei Zhan
CC BY-SA 3.0
2017-10-26T23:47:03.143Z
The following paper on two random spanning trees giving an expander may be helpful in answering your question. https://arxiv.org/abs/0807.1496
Chandra Chekuri
<graph-theory><spanning-tree>
Girth of graphs that decompose into two disjoint union of spanning trees
Hsien-Chih Chang 張顯之
# Girth of graphs that decompose into two disjoint union of spanning trees

(Asked by: username_0 on 2017-10-25)

Let $G$ be an $n$-node graph that can be decomposed into two disjoint union of spanning trees. In particular, $G$ has $2n-2$ edges.

It is not hard to show that the girth of $G$ is at most $O(\log n)$. However, I don't have an example with girth bigger than $4$.

> Do we have an example of such graph whose girth is $\Theta(\log n)$, or is there a way to prove an even better upper bound?

I wonder if there are constant degree expanders that, after removing an appropriate number of edges, can be decomposed into two disjoint union of spanning trees.

**Tags:** graph-theory, spanning-tree
> **Comments:**
> **username_1**: Not sure if this can be generalized, but here is a graph on $\mathbb{Z}/2n\mathbb{Z}$ with girth $6$, where $(x,y)\in E$ iff $x-y$ has the following values: $\pm 1$, or $\pm 2p$ when $x$ is even, or $\pm 2q$ when $x$ is odd. Here $p,q,n$ are coprime and $1<p<q-1$. The graph can be decomposed into two Hamiltonian paths with two extra edges.  
> **username_2**: The following paper on two random spanning trees giving an expander may be helpful in answering your question. https://arxiv.org/abs/0807.1496  

---

## 0 answers

