This paper presents a relaxation of the small-gain theorem for the stability analysis of interconnected discrete-time nonlinear systems. The distinctive feature of this relaxation is that separate systems may be unstable, while global asymptotic stability (GAS) of the overall interconnected systems equilibrium is obtained. In addition, a Lyapunov function for the overall interconnected system is explicitly derived. Necessity of the hypothesis of the small-gain theorem is established for a rather general class of GAS nonlinear systems. An illustrative example demonstrates the non-conservatism of the developed small-gain theorem.