We study the stability of competitive Lotka–Volterra systems on large networks. Extending May’s classical result, we show that instability arises from highly connected outlier nodes rather than simply from system size, and we derive degree-based thresholds that guarantee coexistence. To quantify robustness, we introduce the notion of critical coupling—the maximum interaction strength a system can withstand before losing stability—and demonstrate that network clustering enhances stability, suggesting potential adaptive benefits of such structures. Finally, we show that these dynamics can efficiently approximate solutions to hard graph problems such as the maximum independent set, drawing a direct connection between ecological stability and the classical Motzkin–Straus theorem.