In this study, structural connectivity after mild traumatic brain injury (mTBI) was examined from a network perspective, with a particular focus on post-traumatic complaints. Fifty-three patients with and without self-reported complaints at 2 weeks after uncomplicated mTBI were included, in addition to 20 matched healthy controls. Diffusion weighted imaging was performed at 4 weeks post-injury, and neuropsychological tests measuring processing speed and verbal memory were administered at 3 months post-injury to determine cognitive outcome. Structural connectivity was investigated using whole brain tractography and subsequent graph theory analysis. In patients with mTBI, eigenvector centrality within the left temporal pole was lower than in healthy controls. In patients without complaints, global and mean local efficiency were lower than in patients with complaints, although no differences were found between either subgroup and the group of healthy controls. Neuropsychological test scores were similar for patients with mTBI and healthy controls. However, patients with complaints showed higher processing speed than patients without complaints. Within the total mTBI group, a trend was found toward a correlation between lower network clustering and higher processing speed. Additionally, significant correlations were found between higher betweenness centrality values of language areas and lower verbal memory scores in patients with mTBI. In conclusion, our findings may indicate that global graph measures of the structural connectome are associated with pre- and/or non-injury-related factors that determine the susceptibility to developing (persistent) complaints after mTBI. Further, correlations between graph measures and neuropsychological test scores could suggest early compensatory mechanisms to maintain adequate cognitive performance.