1
$\begingroup$

I am not working on graph theory, so my question may be a little bit vague.

Given a graph (directed or undirected), are there any operations (adding/contracting/removing/sliding edges, gluing with certain graphs...) that do not change the number of (directed or undirected) spanning trees?

I am more interested in the directed case, but any ideas are possible to motivate me.

$\endgroup$
6
  • 3
    $\begingroup$ Yes, here's an easy one: take a vertex of degree $1$, and add another vertex of degree $1$ connected to it. $\endgroup$
    – Qiaochu Yuan
    Commented Jun 18 at 17:49
  • $\begingroup$ @QiaochuYuan Oh yes that's a obvious one. What if the graph has no vertex of degree 1, are there any such interesting operations? $\endgroup$
    – Chard
    Commented Jun 19 at 8:58
  • $\begingroup$ Does the first vertex have to be of degree 1? Can't I add a new vertex $v$ of degree 1 connected to /any/ vertex $u$ of the original graph? $u$ must be in any spanning tree of the graph (else it wouldn't be spanning). $v$ must be in any spanning tree T of the new graph, and there is only 1 way to modify each T to include $v$. Thus we have not changed the number of such trees. $\endgroup$
    – DrM
    Commented Jun 22 at 9:12
  • $\begingroup$ @DrM Thanks, but as I said in the previous comment, how about the case without vertex of degree 1? $\endgroup$
    – Chard
    Commented Jun 22 at 9:32
  • 1
    $\begingroup$ My point is that in @QiaochuYuan's example your original graph does not have to have any vertex of degree 1, as long as the new vertex has degree 1. What's more you could add a whole chain of those, x--x--x--x, I guess. $\endgroup$
    – DrM
    Commented Jun 22 at 9:33

1 Answer 1

Reset to default
0
$\begingroup$

More generally -- this answer is basically for undirected graphs, but it should be possible to see how to adapt it:

  • if the original graph is not connected, then it has no spanning trees. We can add as many vertices and edges as we like, providing we do not connect the graph. We can likewise delete as many vertices and edges as we like, providing we do not leave a connected graph.

So let's consider a connected graph.

  • Firstly, regardless of the structure of the original graph, we can build a whole new graph that is itself a tree (i.e. has exactly one spanning tree). We can then connect this to anywhere on the original graph, as described in my comment, providing we only connect by a single edge.

  • Secondly, if the original graph (or some part of it) is a tree, i.e. has exactly one spanning tree, we can move an edge. If we look at the edge v1-v2, there are two possibilities: v1 and v2 both have degree $> 1$, or exactly one of v1 and v2 has degree 1 (if they both have degree 1 then the graph -- since we're considering connected graphs -- only contains v1 and v2 and there is nowhere to move our edge to). If both v1 and v2 have degree >1, then the edge between them connects two subgraphs. We can delete this edge and replace it with an edge connecting any vertex from the subgraph associated with v1 to any vertex from the subgraph associated with v2. If one of v1 and v2, let's say v1, has degree 1, then when we delete the edge v1-v2, we must replace it with a new edge joining v1 to the subgraph. This edge can be from v1 to any vertex of the subgraph.

  • If the original graph (or some part of it) is a tree, we can also delete any vertex of degree 1 and its associated edge (until we run out of vertices/edges).

  • If the original graph contains an $n$-cycle, then this $n$-cycle contributes $n$ possible spanning trees. If we delete an edge from the cycle, then this part of the graph now has a single spanning tree. So, we need to introduce a cycle or cycles elsewhere to compensate. We can introduce an $n$-cycle elsewhere (by finding (or creating using the subgraph gluing described above) a chain of length $n-1$ and connecting its ends), or if $n = rs$ for some integers $r,s$, we can introduce one $r$-cycle and one $s$-cycle, by replacing the original edge with two new edges at different places in the graph.

(If we have a more complex situation, such as cycles within cycles, I think that we can still just consider each cycle separately for this purpose, but I haven't checked that)

  • Regarding "contracting edges", I guess you mean to replace v1-v2-v3 (say) with v1-v3. Obviously you can do this whenever v1-v2-v3 are a chain in a unique spanning tree (i.e. v2 has degree 2 and whatever is going on around v1 and v3 has no cycles either). If we do this when v1-v2-v3 are part of a cycle, then we will change the number of spanning trees and will need to find a way to compensate.

Maybe this gives you some ideas to start off with.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .