Measuring whole brain networks is a promising approach to extract features of autism spectrum disorder (ASD), a brain disorder of widespread regions. Objectives of this study were to evaluate properties of resting-state functional brain networks in children with and without ASD and to evaluate their relation with social impairment severity. Magnetoencephalographic (MEG) data were recorded for 21 children with ASD (7 girls, 60-89 months old) and for 25 typically developing (TD) control children (10 girls, 60-91 months old) in a resting state while gazing at a fixation cross. After signal sources were localized onto the Desikan-Killiany brain atlas, statistical relations between localized activities were found and evaluated in terms of the phase lag index. After brain networks were constructed and after matching with intelligence using a coarsened exact matching algorithm, ASD and TD graph theoretical measures were compared. We measured autism symptoms severity using the Social Responsiveness Scale and investigated its relation with altered small-worldness using linear regression models. Children with ASD were found to have significantly lower small-worldness in the beta band (p = 0.007) than TD children had. Lower small-worldness in the beta band of children with ASD was associated with higher Social Responsiveness Scale total t-scores (p = 0.047). Significant relations were also inferred for the Social Awareness (p = 0.008) and Social Cognition (p = 0.015) sub-scales. Results obtained using graph theory demonstrate a difference between children with and without ASD in MEG-derived resting-state functional brain networks, and the relation of that difference with social impairment. Combining graph theory and MEG might be a promising approach to establish a biological marker for ASD.