Colloidal gels formed by arrested phase separation are found widely in agriculture, biotechnology, and advanced manufacturing; yet, the emergence of elasticity and the nature of the arrested state in these abundant materials remains unresolved. Here, the quantitative agreement between integrated experimental, computational, and graph theoretic approaches are used to understand the arrested state and the origins of the gel elastic response. The micro-structural source of elasticity is identified by the l-balanced graph partition of the gels into minimally interconnected clusters that act as rigid, load bearing units. The number density of cluster-cluster connections grows with increasing attraction, and explains the emergence of elasticity in the network through the classic Cauchy-Born theory. Clusters are amorphous and iso-static. The internal cluster concentration maps onto the known attractive glass line of sticky colloids at low attraction strengths and extends it to higher strengths and lower particle volume fractions.