Even after recovery from the COVID-19 infection, there have been a multitude of cases reporting post-COVID neurological symptoms including memory loss, brain fog, and attention deficit. Many studies have observed localized microstructural damages in the white matter regions of COVID survivors, indicating potential damage to the axonal pathways in the brain. Therefore, in this study, we have investigated the global impact of localized damage to white matter tracts using graph theoretical analysis of the structural connectome of 45 COVID-recovered subjects and 30 Healthy Controls (HCs). We have implemented Diffusion Tensor Imaging based reconstruction followed by deterministic tractography to extract structural connections among different regions of the brain. Interpreting this structural connectivity as weighted undirected graphs, we have used graph theoretical measures like global efficiency, characteristic path length (CPL), clustering coefficient (CC), modularity, Fiedler value, and assortativity coefficient to quantify the global integration, segregation, and robustness of the brain networks. We statistically compare the cohorts based on these graph measures by employing permutation testing for 100,000 permutations. Post multiple comparisons error correction, we find that the COVID-recovered cohort shows a reduction in global efficiency and CC while they exhibit higher modularity and CPL. This disruption of the balance between global integration and segregation indicates the loss of small-world property in COVID survivors' connectomes which has been linked with other disorders such as cognitive impairment and Alzheimer's. Overall, our study sheds light on the alterations in structural connectivity and its role in post-COVID symptoms.