An Extension of the Win Theorem: Counting the Number of Maximum Independent Sets

Win proved a well-known result that the graph G of connectivity κ(G) with α(G) ≤ κ(G) + k − 1 (k ≥ 2) has a spanning k-ended tree, i.e., a spanning tree with at most k leaves. In this paper, the authors extended the Win theorem in case when κ(G) = 1 to the following: Let G be a simple connected graph of order large enough such that α(G) ≤ k + 1 (k ≥ 3) and such that the number of maximum independent sets of cardinality k + 1 is at most n − 2k − 2. Then G has a spanning k-ended tree.