Spatial heterogeneity of both humans and water may influence the spread of cholera, which is an infectious disease caused by an aquatic bacterium. To incorporate spatial effects, two models of cholera spread are proposed that both include direct (rapid) and indirect (environmental/water) transmission. The first is a multi-group model and the second is a multi-patch model. New mathematical tools from graph theory are used to understand the dynamics of both these heterogeneous cholera models, and to show that each model (under certain assumptions) satisfies a sharp threshold property, which de- termines whether cholera dies out or persists in the population. Specifically, Kirchhoff’s matrix tree theorem is used to investigate the dependence of the disease threshold on the patch connectivity and water movement (multi-patch model), and also to establish the global dynamics of both models.