Applications of the probabilistic method in graph theory

The probabilistic method is a powerful, non-constructive tool with applications in Combinatorics and Discrete Mathematics. It is used for proving the existence of structures with certain properties, without actually constructing them. It follows this structure: in order to prove the existence of a specific object, one chooses an appropriate probability space and estimates the probability that one of its objects has the wanted property. Then, if this probability is greater than 0, one concludes that such a structure exists. In Graph Theory, this method can be applied to a variety of different problems. This thesis aims to show two of these applications. The first one will prove the existence of tournaments with many Hamiltonian paths, whereas the second will concern the Lovász Local Lemma and the non-repetitive colouring of the edges of graphs.