Chapter 4

Connectivity and Traversability

Section 4.1 Connectivity: Properties and Structure

Camino Balbuena

Universitat Politècnica de Catalunya, Spain

Josep Fàbrega

Universitat Politècnica de Catalunya, Spain

Miquel Àngel Fiol

Universitat Politècnica de Catalunya, Spain


Connectivity is one of the central concepts of graph theory, from both a theoretical and a practical point of view. Its theoretical implications are mainly based on the existence of nice max-min characterization results, such as Menger's theorems. In these theorems, one condition which is clearly necessary also turns out to be sufficient. Moreover, these results are closely related to some other key theorems in graph theory: Ford and Fulkerson's theorem about flows ...

Get Handbook of Graph Theory, 2nd Edition now with O’Reilly online learning.

O’Reilly members experience live online training, plus books, videos, and digital content from 200+ publishers.