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 $\kappa(G)$ with $\alpha(G) \leq \kappa(G) + k - 1$ $(k\geq2)$ 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 $\kappa(G)=1$ to the following: Let $G$ be a simple connected graph of order large enough such that $\alpha(G)\leq k+1$ $(k\geq3)$ 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.