[Math] Find edge disjoint spanning tree subgraph between A and B

algorithmsgraph theory

Given an undirected graph G(V,E). A and B are elements of V. Identify a subgraph of G containing A & B with 2 edge disjoint spanning trees (or prove one doesn't exist).

I have found several sources stating to convert the problem to a directed graph and use max-flow min-cut.

https://stackoverflow.com/questions/3271763/how-to-find-two-disjoint-spanning-trees-of-an-undirected-graph

I'm not seeing how this proves edge disjoint spanning trees (only edge disjoint paths). I have seen it cited multiple times, so I am guessing I am just missing something.

Best Answer

The answers to the question you linked are not all correct. In particular, the answer relating to maximum flow computation is wrong. Let me first give you an example showing that this answer is wrong and then further readings stating correct algorithms for finding edge-disjoint trees in a graph.

Consider the following graph:

Example Graph

This graph obviously admits a flow of value 2 between any two vertices. However, it does not admit 2 edge-disjoint spanning trees. Assume such two trees $T_1$ and $T_2$ would exist.

  • Edges $(2,6)$ and $(3,7)$ may not be contained in the same tree, otherwise the other tree would not be connected. Let $(2,6) \in T_1$.
  • Either $\{(2,1), (1,3)\}$ or $\{(2,4),(4,3)\}$ must be contained in $T_1$, otherwise node 3 is not connected to $T_1$.
  • Either node 1 or node 4 cannot be connected to $T_2$.

Thus, the given graph fulfills the requirement that between every two vertices there exists a flow of value at least two, but the graph does not admit two edge-disjoint trees.

Luckily, another answer to the question you linked is correct: The works of Tutte [1] and Nash-Williams [2] give characterizations of the graphs that admit $k$ edge-disjoint trees as well as algorithms computing these trees.

In the above example, consider the partition $P = \{\{1\}, \{2,6\}, \{3,7\}, \{4\}, \{5\}, \{8\}\}$ for $r = 6$. There are 8 edges with endpoints in different sets of the partition. However, the characterization of Tutte and Nash-Williams requires there to be $k (r - 1) = 2 \cdot 5 = 10$ such edges. Therefore, the above example does not fulfill the conditions.

Since the author of the original answer only gave the authors of the papers, here are the full references to the two papers.

[1] On the Problem of Decomposing a Graph into n Connected Factors, Tutte, 1961, Journal of the London Mathematical Society s1-36(1), pages 221-230

[2] Edge-Disjoint Spanning Trees of Finite Graphs, Nash-Williams, 1961, Journal of the London Mathematical Society s1-36(1), pages 445-450

Related Question