Besides being a classical research topic at the junction of combinatorics and probability with applications in several other disciplies, random graphs and their phase transitions have been attracting the interest of the statistical physics community. From a statistical physics viewpoint, random graphs can be viewed as disordered systems, real-world examples of which include glasses and spin glasses. Physicists have thus brought to bear techniques centered around the notion of "replica symmetry breaking", thereby putting forward a multitude of predictions. In this course we will learn about the present state of the art with respect to rigorising these predictions, and about the new mathematical tools developed over the recent years. Additionally, we will look at applications, particularly in the area of Bayesian inference.