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.