Representations of social categories help us make sense of the social world, supporting predictions and explanations about groups and individuals. In an experiment with 156 participants, we explore whether children and adults are able to understand category-property associations (such as the association between “girls” and “pink”) in structural terms, locating an object of explanation within a larger structure and identifying structural constraints that act on elements of the structure. We show that children as young as 3-4 years old show signs of structural thinking, and that 5-6 year olds show additional differentiation between structural and nonstructural thinking, yet still fall short of adult performance. These findings introduce structural connections as a new type of non-accidental relationship between a property and a category, and present a viable alternative to internalist accounts of social categories, such as psychological essentialism.