Connectivity

Connectivity is a key property of graphs. The central result on connectivity of graphs is the theorem of Menger, a result of min–max type with several connections in other areas of combinatorics and of combinatorial optimization, besides its relevance in graph theory itself. Some structural results related to connectivity are also presented in this chapter, including a theorem of Tutte on 3-connected graphs. The close notion of edge-connectivity is also discussed at the end of the chapter.