<p>If $G$ has $n$ vertices and $m$ edges, then for any spanning tree $T$ of $G$, each of the $m-n+1$ edges that are not in $T$ may be swapped with any of the edges on the path in $T$ between the endpoints of the non-tree edge. Assuming $G$ is not a multigraph, this gives at least $2(m-n+1)$ different swaps; that is, every $T$ has degree at least $2(m-n+1)$.</p>

<p>This bound is tight: if $G$ has a vertex $v$ adjacent to all others, and $T$ is the spanning tree consisting of all the edges incident to $v$, then the path in $T$ between the endpoints $T$ of every non-tree edge has length exactly two, so each non-tree edge participates in exactly two swaps and $T$ has degree exactly $2(m-n+1)$.</p>

<p>On the other hand if $G$ has girth (shortest cycle length) $g$, then the path in any tree $T$ between the endpoints of any non-tree edge, together with that edge, forms a cycle which must have length at least $g$, so the minimum degree in the tree graph must be at least $(g-1)(m-n+1)$. This bound is tight for some graphs such as the cycle graphs, and complete bipartite graphs, and Moore graphs, since these graphs contain spanning trees for which all non-tree edges induce cycles of length equal to the girth.</p>

<p>However, finding the minimum degree of the tree graph for an arbitrary given graph (equivalently, finding a spanning tree minimizing the sum of lengths of the cycles induced by non-tree edges) is NP-complete: see <a href="https://mpi-inf.mpg.de/~mehlhorn/SelectedTopics/p26-deo.pdf">Deo, Prabhu, and Krishnamoorthy, "Algorithms for Generating Fundamental Cycles in a Graph", <em>ACM TOMS</em> 1982</a>. So finding bounds such as these that are tight for all graphs appears unlikely.</p>

CC BY-SA 3.0
2011-09-26T00:47:39.790Z
Thanks for the excellent answer. Can we find a tight upper-bound that is correct for all graphs?
corwin
CC BY-SA 3.0
2011-09-26T00:52:11.857Z
Also, is there a known upper-bound on the girth of a connected graph with $n$ vertices and $m$ edges?
corwin
CC BY-SA 3.0
2011-09-25T15:30:25.857Z
2011-09-26T14:16:05.747Z
2011-09-26T14:16:05.747Z
David Eppstein
<p>Given a graph $G$, define the tree graph $T(G)$ as a graph whose vertices are the spanning trees of $G$, and there is an edge between two trees if one can be obtained from the other by replacing a single edge. That is there is an edge $(T_1, T_2)$ if there exists two edges $x, y \in G$ such that $T_1 - x = T_2 - y$.</p>

<p>My question is this: are there some non-trivial lower or upper bounds on the degree of the vertex with minimum degree in $T(G)$?</p>

<p>Note: I edited the question (last line) a bit to make it less ambiguous
.</p>

CC BY-SA 3.0
2011-09-25T02:49:44.347Z
Your definition of an edge doesn't make sense. Do you mean "there is an edge between $T_1$ and $T_2$ if there exists two edges $x, y \in G$ such that $T_1 - x + y = T_2$"?
Tyson Williams
CC BY-SA 3.0
2011-09-25T03:27:06.657Z
Yes, sorry I meant edges.
corwin
CC BY-SA 3.0
2011-09-25T07:30:08.040Z
If $G$ is a tree, its tree graph $T(G)$ is a single vertex with degree 0.  On the other hand, if $G$ is a complete graph, every vertex in $T(G)$ has degree $\Theta(n^2)$.  What exactly do you mean by "non-trivial"?
Jeffε
CC BY-SA 3.0
2011-09-25T07:43:08.463Z
it is also clearly greater than the connectivity of $G$ minus 1. Is this trivial? You should expand your question with what you know about the problem already, so that we can judge what you consider trivial and what you don't.
Artem Kaznatcheev
CC BY-SA 3.0
2011-09-25T13:12:23.093Z
@Jeffe I don't think $\Theta(n^2)$ for a complete graph is correct. Take for example a tree that is a line. Removing an edge from the tree will disconnect the tree into two groups $S$ and $T$. Now there are $|S|\cdot|T|$ edges that can be added to make it a tree again. Taking over all edges of that tree we see that there are $\Theta(n^3)$ nearby trees.
corwin
CC BY-SA 3.0
2011-09-25T13:22:31.363Z
When I wrote "non-trivial" I meant "not obvious". But to be more concrete, I am looking for close lower and upper bounds on the degree of the vertex with **minimum** degree in $T(G)$. I am looking for bounds that hold for all graphs, but also bounds that hold for the complete graph are good too.  I am more interested in an upper bound.
corwin
CC BY-SA 3.0
2011-09-26T15:27:10.983Z
Sorry, you're right.  Every node in the tree graph of a complete graph has degree between $\Omega(n^2)$ [a star] and $O(n^3)$ [a path].
Jeffε
<graph-theory><tree>
Minimum degree of the "tree graph"
corwin
# Minimum degree of the "tree graph"

(Asked by: username_0 on 2011-09-25)

Given a graph $G$, define the tree graph $T(G)$ as a graph whose vertices are the spanning trees of $G$, and there is an edge between two trees if one can be obtained from the other by replacing a single edge. That is there is an edge $(T\_1, T\_2)$ if there exists two edges $x, y \in G$ such that $T\_1 - x = T\_2 - y$.

My question is this: are there some non-trivial lower or upper bounds on the degree of the vertex with minimum degree in $T(G)$?

Note: I edited the question (last line) a bit to make it less ambiguous
.

**Tags:** graph-theory, tree

> **Comments:**
> **username_1**: Your definition of an edge doesn't make sense. Do you mean "there is an edge between $T_1$ and $T_2$ if there exists two edges $x, y \in G$ such that $T_1 - x + y = T_2$"?  
> **username_0**: Yes, sorry I meant edges.  
> **username_2**: If $G$ is a tree, its tree graph $T(G)$ is a single vertex with degree 0.  On the other hand, if $G$ is a complete graph, every vertex in $T(G)$ has degree $\Theta(n^2)$.  What exactly do you mean by "non-trivial"?  
> **username_3**: it is also clearly greater than the connectivity of $G$ minus 1. Is this trivial? You should expand your question with what you know about the problem already, so that we can judge what you consider trivial and what you don't.  
> **username_0**: @Jeffe I don't think $\Theta(n^2)$ for a complete graph is correct. Take for example a tree that is a line. Removing an edge from the tree will disconnect the tree into two groups $S$ and $T$. Now there are $|S|\cdot|T|$ edges that can be added to make it a tree again. Taking over all edges of that tree we see that there are $\Theta(n^3)$ nearby trees.  
> **username_0**: When I wrote "non-trivial" I meant "not obvious". But to be more concrete, I am looking for close lower and upper bounds on the degree of the vertex with **minimum** degree in $T(G)$. I am looking for bounds that hold for all graphs, but also bounds that hold for the complete graph are good too.  I am more interested in an upper bound.  
> **username_2**: Sorry, you're right.  Every node in the tree graph of a complete graph has degree between $\Omega(n^2)$ [a star] and $O(n^3)$ [a path].  

---

## 1 answers

### Answer by username_4 on 2011-09-25. Score: 12

If $G$ has $n$ vertices and $m$ edges, then for any spanning tree $T$ of $G$, each of the $m-n+1$ edges that are not in $T$ may be swapped with any of the edges on the path in $T$ between the endpoints of the non-tree edge. Assuming $G$ is not a multigraph, this gives at least $2(m-n+1)$ different swaps; that is, every $T$ has degree at least $2(m-n+1)$.

This bound is tight: if $G$ has a vertex $v$ adjacent to all others, and $T$ is the spanning tree consisting of all the edges incident to $v$, then the path in $T$ between the endpoints $T$ of every non-tree edge has length exactly two, so each non-tree edge participates in exactly two swaps and $T$ has degree exactly $2(m-n+1)$.

On the other hand if $G$ has girth (shortest cycle length) $g$, then the path in any tree $T$ between the endpoints of any non-tree edge, together with that edge, forms a cycle which must have length at least $g$, so the minimum degree in the tree graph must be at least $(g-1)(m-n+1)$. This bound is tight for some graphs such as the cycle graphs, and complete bipartite graphs, and Moore graphs, since these graphs contain spanning trees for which all non-tree edges induce cycles of length equal to the girth.

However, finding the minimum degree of the tree graph for an arbitrary given graph (equivalently, finding a spanning tree minimizing the sum of lengths of the cycles induced by non-tree edges) is NP-complete: see [Deo, Prabhu, and Krishnamoorthy, "Algorithms for Generating Fundamental Cycles in a Graph", *ACM TOMS* 1982](https://mpi-inf.mpg.de/~mehlhorn/SelectedTopics/p26-deo.pdf). So finding bounds such as these that are tight for all graphs appears unlikely.

> **Comments:**
> **username_0**: Thanks for the excellent answer. Can we find a tight upper-bound that is correct for all graphs?  
> **username_0**: Also, is there a known upper-bound on the girth of a connected graph with $n$ vertices and $m$ edges?  

---

