Tangles and Tree Width: A New Connectivity Measure and Some Consequences

Bruce Reed, Paris and São Paulo

A graph is a set of vertices and an adjacency relation which indicates which pairs of vertices are joined by an edge. Thus, graph theory is essentially the study of connectivity. How then does one measure the connectivity of a graph?

Measuring the connectivity between two vertices is straightforward. Two vertices are said to be k-connected if there are k internally vertex disjoint paths between them. A classical theorem of Menger states that vertices a and b are k-connected in a graph G precisely if there is no set X of fewer than k vertices such that a and b lie in different components of G − X. Standard alternating paths techniques, allow us to find either k internally vertex disjoint a-b paths or such a set X efficiently.

An appropriate definition of a highly connected graph, or of a highly connected piece of a graph is more difficult. The classical approach is to call a graph k-connected if every pair of its vertices is k-connected. This definition, although natural, does not capture the kind of connectivity that will concern us. It focuses on local properties rather than global ones. To illustrate what we mean, we consider the hexagonal lattice L. Then L has maximum degree three and hence contains no 4-connected subgraph. On the other hand, if X is a set of at most three vertices of L then L − X is either connected or has two components, one of which is a vertex. Similarly, if X is a set of at most k vertices then the largest component of L − X contains all but at most k^{2} of the vertices of L. Thus, no cutset of size k “globally disconnects” L. One of the goals of this paper is to introduce its readers to a connectivity invariant, the bramble number, which measures global connectivity.

Having done so, we will examine those graphs for which this invariant is bounded by a given k. If the bramble number of G is at most two then G is a forest. It turns out that for any k, the graphs with bramble number at most k have a “tree-like” structure. How tree-like depends on the value of k. We will present a precise duality theorem after we have developed the requisite definitions. Now, such tree-like structures are easy to deal with. For example, we will develop efficient algorithms for resolving seemingly difficult (i.e. NPcomplete) problems on graphs whose bramble number is bounded. We will also see that many difficult conjectures can be resolved when restricted to such graphs.

We will also examine the structure of graphs with large bramble number. It turns out that if a graph has large bramble number then it must contain a subdivision of a large piece of the hexagonal lattice. This fact allows us to resolve many difficult questions on such graphs.

Combining the two complementary types of results discussed above has proven very fruitful. We will present some of the many results obtained using this technique. We will also discuss an assortment of other results which elucidate the dual notions of brambles and tree-structures. The most important of these is a theorem which states that every graph can be decomposed into a tree structure of pieces each of which corresponds to a maximally connected part of the graph.