Tutte's 5-flow conjecture

The aim of this thesis is to show and put together the results, obtained so far, useful to tackle a conjecture of graph theory proposed in 1954 by William Thomas Tutte. The conjecture in question is Tutte's 5-flow conjecture, which states that every bridgeless graph admits a nowhere-zero 5-flow, namely a flow with non-zero integer values between -4 and 4. We will start by giving some basics on graph theory, useful for the followings, and proving some results about flows on oriented graphs and in particular about the flow polynomial. Next we will treat two cases: graphs embeddable in the plane $\mathbb{R}^2$ and graphs embeddable in the projective plane $\mathbb{P}^2$. In the first case we will see the correlation between flows and colorings and prove a theorem even stronger than Tutte's conjecture, using the 4-color theorem. In the second case we will see how in 1984 Richard Steinberg used Fleischner's Splitting Lemma to show that there can be no minimal counterexample of the conjecture in the case of graphs in the projective plane. In the fourth chapter we will look at the theorems of François Jaeger (1976) and Paul D. Seymour (1981). The former proved that every bridgeless graph admits a nowhere-zero 8-flow, the latter managed to go even further showing that every bridgeless graph admits a nowhere-zero 6-flow. In the fifth and final chapter there will be a short introduction to the Tutte polynomial and it will be shown how it is related to the flow polynomial via the Recipe Theorem. Finally we will see some applications of flows through the study of networks and their properties.