The Cohesive Degree Condition of Non-separating Subtree Problems in Graph Partition

This paper focuses on a conjecture proposed by Locke in 1998 about the partition of subtrees in graphs, that is, all 2m-cohesive degree condition graphs contain trees with arbitrary m vertices, and the graph remains connected after removing the subtrees. Here, 2m-cohesive means that the sum of the degrees and the distance for any two vertices is greater than or equal to 2m. In this paper, we discuss the cases according to the minimum degree of the graphs, and use the method of induction hypothesis on the number of vertices. In addition, we give the existing condition of the cohesive form of any subtree. Based on the conclusion of Locke’s conjecture, this paper also generalizes to the tree partition problem of k-connected graphs and part of the conclusions of Mader’s conjecture. The results in this paper proved that the conjecture holds for all tree classes except stars and double stars.