The human brain is a complex, interconnected network par excellence. Accurate and informative mapping of this human connectome has become a central goal of neuroscience. At the heart of this endeavor is the notion that brain connectivity can be abstracted to a graph of nodes, representing neural elements (e.g., neurons, brain regions), linked by edges, representing some measure of structural, functional or causal interaction between nodes. Such a representation brings connectomic data into the realm of graph theory, affording a rich repertoire of mathematical tools and concepts that can be used to characterize diverse anatomical and dynamical properties of brain networks. Although this approach has tremendous potential — and has seen rapid uptake in the neuroimaging community — it also has a number of pitfalls and unresolved challenges which can, if not approached with due caution, undermine the explanatory potential of the endeavor. We review these pitfalls, the prevailing solutions to overcome them, and the challenges at the forefront of the field. •Reviews progress and pitfalls associated with graph analysis of connectomic data•Focuses on issues associated with building an analyzing such graphs•Discusses characteristics of ideal connectomic map•Considers issues associated with accurate node and edge definition•Discusses key issues associated with analyzing and interpreting graph models