6 THE BASIC METHOD the number of vertices u that do not lie in the union of the sets c(v)of the vertices chos sen so far is r.By the ass umption,the sum of the cardinalities of the sets C(u over all such uncovered vertices u is at least r(+1),and hence,by averaging.there is a vertex v that belongs to at least r(+1)/n such sets C(u).Adding this v to the set of chosen vertices we observe that the number of uncovered vertices is now at mostr(1-(+1)/n).It follows that in each iteration of the above procedure the number of u ncovered vertices decreases by a factor of 1-(6+1)/n and hence after n In(6+1)/(6+1)steps there will be at most n/(6+1)yet uncovered vertices that can now be added to the set of chosen vertices to form a dominating set of size at most equal to the one in the conclusion of Theorem 1.2.2. Combining this ith some ideas of Podderyugin and Matula,very efficient algorithm to decide if a given undirected graph on n vertices is,say.n/2 edge-connected.A cut in a graph G=(V,E)is a partition of the set of vertices V into two nonempty disjoint sets V=ViUV2.If Vi and we say that the cut separates v and v2. The size of the cut is the number of edges of G having one end in Vi and another end in V2.In fact,we sometimes identify the cut with the set of these edges.The edge connectiviry of G is the minimum size of a cut of G. The following lemma is due to Podderyugin and Matula (independently). Lemma 1.2.3 Let G =(V,E)be a graph with minimum degree 6 and letV =ViUV2 be a cut of size smaller than 6 in G.Then every dominating set U of G has vertices in Vi and in V2 Proof.Suppose this is false and UVi.Choose,arbitrarily,a vertex V2 and let v1,v2,...,vs be 6 of its neighbors.For each i,1 <i6,define an edge e of the given cut as follows;if v Vi then e=fv,vi,otherwise,v;E V2 and since U is dominating there is at least one vertex uU such that u,is an edge;take such a u and put e u,vi).The 6 edges e,...,e are all dist and all lie in the given cut,contradicting the assumption that its size is less than This completes the proof. ■ Let G=(V,E)be a graph on n vertices,and suppose we wish to decide if Gis n/2 edge-connected:that is,if its edg vity is at least n/2.Matula showed,by applying Lemma 1.3.that this can be done in time (n).By the remark following the proof of Theorem 1.2.2,we can slightly improve it and get an O(n8/3 log n)algorithm as follows.We first check if the minimum degree 6 of onnected,and the algorithn ends {ui,...,uk}of G where k=O(log n).and it can in fact be found in time O(n).We now find,for each i,2 <i<k,the minimum size s;of a cut that separates u from u.Each of these problems can be solved by solving a standard network flow problem in time see.Tarjan()By Lemma 1.2.3 the edge conectivity ofis simply the minimum between 6 and min2<s.The total time of the algorithm is O(n8/3 logn),as claimed. 6 THE BASIC METHOD the number of vértices u that do not lie in the unión of the sets C(v) of the vértices chosen so far is r. By the assumption, the sum of the cardinalities of the sets C(u) over all such uncovered vértices u is at least r(S + 1), and henee, by averaging, there is a vértex v that belongs to at least r(S + l)/n such sets C{u). Adding this v to the set of chosen vértices we observe that the number of uncovered vértices is now at most r(l — (5 + l)/n). It follows that in each iteration of the above procedure the number of uncovered vértices decreases by a factor of 1 — (5 + l)/n and henee after n ln(í + l)/(¿ + 1) steps there will be at most n/(6 + 1) yet uncovered vértices that can now be added to the set of chosen vértices to form a dominating set of size at most equal to the one in the conclusión of Theorem 1.2.2. Combining this with some ideas of Podderyugin and Matula, we can obtain a very efficient algorithm to decide if a given undirected graph on n vértices is, say, n/2 edge-connected. A cut in a graph G = (V, E) is a partition of the set of vértices V into two nonempty disjoint sets V = V\ U V¿. If v\ e V\ and v-¿ € V2 we say that the cut separates v\ and Vi. The size of the cut is the number of edges of G having one end in Vi and another end in V?. In fact, we sometimes identify the cut with the set of these edges. The edge connectivity of G is the minimum size of a cut of G. The following lemma is due to Podderyugin and Matula (independently). Lemma 1.2.3 Let G = (V,E)bea graph with minimum degree 5 and let V = V\ U V2 be a cut of size smaller than 6 in G Then every dominating set U ofG has vértices in V\ and in V2. Proof. Suppose this is false and í/ C Vi. Choose, arbitrarily, a vértex v £ V2 and let vi, t>2, • • •, vg be S of its neighbors. For each i, 1 < i < S, define an edge e¿ of the given cut as follows; if Vi G Vi then e¿ = {v, Vi}, otherwise, v¿ e V2 and since U is dominating there is at least one vértex u 6 U such that {u, w¿} is an edge; take such a u and put e¿ = {u, v¿}. The S edges ei,... , e¿ are all distinct and all lie in the given cut, contradicting the assumption that its size is less than S. This completes the proof. • Let G = (V,E) be a graph on n vértices, and suppose we wish to decide if G is n/2 edge-connected; that is, if its edge connectivity is at least n/2. Matula showed, by applying Lemma 1.2.3, that this can be done in time 0(n3 ). By the remark following the proof of Theorem 1.2.2, we can slightly improve it and get an 0(n8 / 3 logn) algorithm as follows. We first check if the minimum degree 5 of G is at least n/2. If not, G is not n/2 edge-connected, and the algorithm ends. Otherwise, by Theorem 1.2.2 there is a dominating set U = {ui,... ,Uk} of G, where k = O(logn), and it can in fact be found in time 0(n2 ). We now find, for each i, 2 < i < k, the minimum size s¿ of a cut that separates u\ from u¿. Each of these problems can be solved by solving a standard network flow problem in time 0(n8 / 3 ) [see, e.g., Tarjan (1983)]. By Lemma 1.2.3 the edge connectivity of G is simply the minimum between 5 and min2<¿<fc s¿. The total time of the algorithm is 0(ns / 3 log n), as claimed