# Girth of graphs that decompose into two disjoint union of spanning trees

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.

• 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. – Willard Zhan Oct 25 '17 at 22:23
• The following paper on two random spanning trees giving an expander may be helpful in answering your question. arxiv.org/abs/0807.1496 – Chandra Chekuri Oct 26 '17 at 23:47