A counterexample for the proof of implication conjecture on independent spanning trees

• We disprove an earlier result on edge-independent trees published by Khuller and Schieber in [S. Khuller, B. Schieber, On independent spanning trees, Information Processing Letters 42 (6) (1992) 321–323].
• We show that the algorithm by Khuller and Schieber fails in certain scenarios.
• While the implication conjecture may still hold true, the previously known proof is shown to be incorrect.

Khuller and Schieber (1992) in [1] developed a constructive algorithm to prove that the existence of k-vertex independent trees in a k-vertex connected graph implies the existence of k-edge independent trees in a k-edge connected graph. In this paper, we show a counterexample where their algorithm fails.