We performed an EEG graph analysis on data from 31 typical readers (22.27 ± 2.53 y/o) and 24 dyslexics (22.99 ± 2.29 y/o), recorded while they were engaged in an audiovisual task and during resting-state. The task simulates reading acquisition as participants learned new letter-sound mappings via feedback. EEG data was filtered for the delta (0.5–4 Hz), theta (4–8 Hz), alpha (8–13 Hz), and beta (13–30 Hz) bands. We computed the Phase Lag Index (PLI) to provide an estimate of the functional connectivity between all pairs of electrodes per band. Then, networks were constructed using a Minimum Spanning Tree (MST), a unique sub-graph connecting all nodes (electrodes) without loops, aimed at minimizing bias in between groups and conditions comparisons. Both groups showed a comparable accuracy increase during task blocks, indicating that they correctly learned the new associations. The EEG results revealed lower task-specific theta connectivity, and lower theta degree correlation over both rest and task recordings, indicating less network integration in dyslexics compared to typical readers. This pattern suggests a role of theta oscillations in dyslexia and may reflect differences in task engagement between the groups, although robust correlations between MST metrics and performance indices were lacking.