In this BSc thesis we investigate nowhere-zero flows on graphs. It turns out that this concept is very useful in graph theory itself, as well as in practice.
Before introducing the concept of nowhere-zero flows we make a short review, along with some examples, of some notions in graph theory and in group theory, which are necessary for the understanding of this BSc thesis. We then define the concept of flows and nowhere-zero flows, and illustrate them with examples. We focus on flows with values in abelian groups. We present an important theorem of W. T. Tutte, which gives a correspondence between nowhere-zero k-flows with nowhere-zero Z_k-flows. We prove the theorem and illustrate it with an example. Lastly, we present and prove some results about the existence of nowhere-zero k-flows for small values of k. We mention also two well-known Tutte's conjectures on these flows.
|
