We are not individuals, we are much better described as ecosystems due to trillions of bacteria and other microorganisms that inhabit us. We now know that gut microbiota can greatly influence many physiological parameters that in turn may impact several cognitive functions, such as learning, memory, and decision making processes. This mutualistic symbiotic relation known as the gut-brain axis is also constrained by lyfestyle factors such as dietary habits i.e. animal protein and lipids intake. Using a novel combination of Machine Learning and Network Theory techniques, we provide evidence from an indigenous population in Guerrero Mexico, that both brain and gut-microbiota connectivity, evaluated by Minimum Spanning Tree as the critical backbone of information flow, diminish under either low protein or lipids intake. We discuss how this loss of connectivity may translate into a reduction of brain criticality.