111.4 ConnectivityLet G = (V,E) be a graph. A maximal connected subgraph of Gis called a component of G. Note that a component, being connected, iscomponenalways non-empty; the empty graph, therefore, has no components.Fig.1.4.1.Agraphwith three componnts, and arspanning connected subgraph in each componentIf A, B V and X CVUE are such that every A-B path in Gcontains a vertex or an edge from X, we say that X separates the sets Aseparateand B in G. Note that this implies AnB C X. More generally we saythat X separates G if G-X is disconected, that is, if X separates inG some two vertices that are not in X. A separating set of vertices is aseparator. Separating sets of edges have no generic name, but some suchseparatorsets do; see Section 1.9 for the definition of cuts and bonds. A vertexcutvertexwhich separates two other vertices of the same component is a cutuerter,and an edge separating its ends is a bridge. Thus, the bridges in a graphbridgeare precisely those edges that do not lie on any cycle.y.WYeFiq.1.4.2.A graphwith cutvertiwandbridgee=ryThe unordered pair (A, B] is a separation of G if AUB = V and Gseparationhas no edge between AB and BA. Clearly, the latter is equivalentto saying that AnB separates A from B. If both AB and B\A arenon-empty, the separation is proper. The number [An B| is the order oftheseparationfA.BG is called k-connected (for k e N) if [G > k and G- X is connected k-connectedfor every set X V with X|< k. In other words, no two vertices of Gare separated by fewer than k other vertices. Every (non-empty) graphis O-connected, and the 1-connected graphs are precisely the non-trivials. The greatest integer k such that G is k-connectedconnected graphs.iy)aK(G)disconnected or a Kl, and k(K") = n -1 for all n ≥ 1.1.4 Connectivity 11 Let G = (V,E) be a graph. A maximal connected subgraph of G is called a component of G. Note that a component, being connected, is component always non-empty; the empty graph, therefore, has no components. Fig. 1.4.1. A graph with three components, and a minimal spanning connected subgraph in each component If A, B ⊆ V and X ⊆ V ∪ E are such that every A–B path in G contains a vertex or an edge from X, we say that X separates the sets A separate and B in G. Note that this implies A ∩ B ⊆ X. More generally we say that X separates G if G − X is disconnected, that is, if X separates in G some two vertices that are not in X. A separating set of vertices is a separator . Separating sets of edges have no generic name, but some such separator sets do; see Section 1.9 for the definition of cuts and bonds. A vertex cutvertex which separates two other vertices of the same component is a cutvertex , and an edge separating its ends is a bridge. Thus, the bridges in a graph bridge are precisely those edges that do not lie on any cycle. v w e x y Fig. 1.4.2. A graph with cutvertices v, x, y, w and bridge e = xy The unordered pair { A, B } is a separation of G if A∪B = V and G separation has no edge between A
B and B
A. Clearly, the latter is equivalent to saying that A ∩ B separates A from B. If both A
B and B
A are non-empty, the separation is proper . The number |A∩B| is the order of the separation { A, B }. G is called k-connected (for k ∈ N) if |G| > k and G−X is connected k-connected for every set X ⊆ V with |X| < k. In other words, no two vertices of G are separated by fewer than k other vertices. Every (non-empty) graph is 0-connected, and the 1-connected graphs are precisely the non-trivial connected graphs. The greatest integer k such that G is k-connected is the connectivity κ(G) of G. Thus, κ(G) = 0 if and only if G is connectivity κ(G) disconnected or a K1, and κ(Kn) = n − 1 for all n 1.