This work analyzes and characterizes the spread of the COVID-19 disease in Mexico, using complex networks and optimization approaches. Specifically, we present two methodologies based on the principle of the rupture for the GC and Newton's law of motion to quantify the robustness and identify the Mexican municipalities whose population causes a fast spread of the SARS-CoV-2 virus. Specifically, the first methodology is based on several characteristics of the original version of the Vertex Separator Problem, and the second is based (...) on a new mathematical model. By solving VSP, we can find nodes that cause the rupture of the giant component. On the other hand, solving the NLM can find more influential nodes for the entire system’s development. Specifically, we present an analysis using a coupled social network model with information about the main characteristics of the contagion and deaths caused by COVID-19 in Mexico for 19 months. This work aims to show through the approach of complex networks how the spread of the disease behaves, and, thus, researchers from other areas can delve into the characteristics that cause this behavior. (shrink)