In this note, we consider the sabotage game played on random graphs, as an illustration of how elementary techniques from the study of random graphs can be put to use to investigate graph games which are of independent interest to modal logicians. We show that Traveller almost surely has a winning strategy in the sabotage game played on random (multi)graphs, given by the Gilbert-Erdős-Rényi model with fixed edge probability. In the model with decreasing edge probability, we consider the emergence of sure-win graphs for Traveller—graphs where Traveller has a winning strategy for any choice of start and goal vertices. By relating the sure-win property to extension statements for random graphs, we give rough bounds on the threshold function for sure-win graphs: in terms of asymptotic dominance, the threshold function decays no slower than \(\root 3 \of {\ln n/n}\) , but no faster than \(\sqrt{\ln n/n}\) . We conclude with a few remarks on the logical characterisability of winning strategies, and prove that the existence of a winning strategy for Traveller is not first-order characterisable over finite models.