During childhood, brain structure and function changes substantially. Recently, graph theory has been introduced to model connectivity in the brain. Small-world networks, such as the brain, combine optimal properties of both ordered and random networks, i.e., high clustering and short path lengths. We used graph theoretical concepts to examine changes in functional brain networks during normal development in young children. Resting-state eyes-closed electroencephalography (EEG) was recorded (14 channels) from 227 children twice at 5 and 7 years of age. Synchronization likelihood (SL) was calculated in three different frequency bands and between each pair of electrodes to obtain SL-weighted graphs. Mean normalized clustering index, average path length and weight dispersion were calculated to characterize network organization. Repeated measures analysis of variance tested for time and gender effects. For all frequency bands mean SL decreased from 5 to 7 years. Clustering coefficient increased in the alpha band. Path length increased in all frequency bands. Mean normalized weight dispersion decreased in beta band. Girls showed higher synchronization for all frequency bands and a higher mean clustering in alpha and beta bands. The overall decrease in functional connectivity (SL) might reflect pruning of unused synapses and preservation of strong connections resulting in more cost-effective networks. Accordingly, we found increases in average clustering and path length and decreased weight dispersion indicating that normal brain maturation is characterized by a shift from random to more organized small-world functional networks. This developmental process is influenced by gender differences early in development.