101.The BasicsTheorem 1.3.4. (Alon, Hoory & Linial 2002)Let G be a graph. If d(G) ≥ d ≥ 2 and g(G) ≥ g e N then [G| ≥ no(d, g)One aspect of Theorem 1.3.4 is that it guarantees the existence ofa short cycle compared with |Gj. Using just the easy minimum degreeversion of Exercise 6, we get the following rather general bound:[2.3.1]Corollary 1.3.5. If 8(G) ≥ 3 then g(G) < 2log /G)Proof. If g := g(G) is even then29/21= 29/2 + (29/2 = 2) > 29/2,no(3, 9) = 22-1while if g is odd then2(g-1)/2 1329/2-2>29/2.no(3,g)=1+32-1V2口As G[ ≥ no(3, g), the result follows.A walk (of length k) in a graph G is a non-empty alternating se-walkquence Voeouiei...ek-iuk of vertices and edges in G such that e, -ui, Ui+1] for all i<k. If vo = vs, the walk is closed. If the verticesin a walk are all distinct, it defines an obvious path in G. In general,every walk between two vertices contains a path between these vertices(proof?).1.4 ConnectivityconnectedA non-empty graph G is called connected if any two of its vertices arelinked by a path in G. If U C V(G) and G[U] is connected, we alsocall U itself connected (in G). Instead of 'not connected' we usually say'disconnected'.[1.5.2]Proposition 1.4.1. The vertices of a connected graph G can always beenumerated, say as vi,..., Un, so that G, : G[vi,..., u,] is connectedfor everyiProof. Pick any vertex as vi, and :assume inductively that i,..,have been chosen for some i< JGJ. Now pick a vertex u e G- G,. As Gis connected, it contains a v-ui path P. Choose as ui+1 the last vertexof P in G-G; then Ui+i has a neighbour in G,. The connectedness of口every G, follows by induction on i.4Weshalloften use terms defined for graphs also for walks, as long as theirmeaning is obvious
10 1. The Basics Theorem 1.3.4. (Alon, Hoory & Linial 2002) Let G be a graph. If d(G) d 2 and g(G) g ∈ N then |G| n0(d, g). One aspect of Theorem 1.3.4 is that it guarantees the existence of a short cycle compared with |G|. Using just the easy minimum degree version of Exercise 6, we get the following rather general bound: [ 2.3.1 ] Corollary 1.3.5. If δ(G) 3 then g(G) < 2 log |G|. Proof . If g := g(G) is even then n0(3, g)=2 2g/2 − 1 2 − 1 = 2g/2 + (2g/2 − 2) > 2g/2, while if g is odd then n0(3, g) = 1+3 2(g−1)/2 − 1 2 − 1 = 3 √2 2g/2 − 2 > 2g/2. As |G| n0(3, g), the result follows. walk A walk (of length k) in a graph G is a non-empty alternating sequence v0e0v1e1 ...ek−1vk of vertices and edges in G such that ei = { vi, vi+1 } for all i<k. If v0 = vk, the walk is closed. If the vertices in a walk are all distinct, it defines an obvious path in G. In general, every walk between two vertices contains4 a path between these vertices (proof?). 1.4 Connectivity connected A non-empty graph G is called connected if any two of its vertices are linked by a path in G. If U ⊆ V (G) and G [U ] is connected, we also call U itself connected (in G). Instead of ‘not connected’ we usually say ‘disconnected’. [ 1.5.2 ] Proposition 1.4.1. The vertices of a connected graph G can always be enumerated, say as v1,...,vn, so that Gi := G [ v1,...,vi ] is connected for every i. Proof . Pick any vertex as v1, and assume inductively that v1,...,vi have been chosen for some i < |G|. Now pick a vertex v ∈ G−Gi. As G is connected, it contains a v–v1 path P. Choose as vi+1 the last vertex of P in G − Gi; then vi+1 has a neighbour in Gi. The connectedness of every Gi follows by induction on i. 4 We shall often use terms defined for graphs also for walks, as long as their meaning is obvious.
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.
121.The BasicsIf JG| > 1 and G-F is connected for every set F E of fewerl-edgthan I edges, then G is called l-edge-connected. The greatest integer connectedsuch that G is l-edge-connected is the edge-connectivity A(G) of G. Inedgeconnectivity particular, we have (G) = O if G is disconnected.入(G)GFig. 1.4.3. The octahedron G (left) with x(G) = 入(G) = 4and a graph H with k(H) = 2 but (H) = 4Proposition 1.4.2. If G is non-trivial then k(G) ≤ ^(G) ≤ (G)Proof. The second inequality follows from the fact that all the edgesincident with a fixed vertex separate G. To prove the first, let F be anyminimal subset of E such that G - F is disconnected. We show thatk(G) ≤[F}.Suppose first that G has a vertex u that is not incident with an edgein F. Let C be the component of G - F containing v. Then the verticesof C that are incident with an edge in F separate u from G- C. Sinceno edge in F has both ends in C (by the minimality of F), there are atmost [F| such vertices, giving k(G) ≤ [F as desired.Suppose now that every vertex is incident with an edge in F. Let ybe any vertex, and let C be the component of G-F containing u. Thenw of v with ww F lie in C and are incident with distincttheneighboedges in F, giving dc(u) ≤ [F]. As Nc(u) separates u from all the othervertices in G, this yields k(G) < [Funless there are no other vertices.i.e. unless (uN(u) = V. But v was an arbitrary vertex. So we may口assume that G is complete, giving r(G) = ^(G) = [G| - 1.By Proposition 1.4.2, high connectivity requires a large minimumdegree. Conversely, large minimum degree does not ensure high connec-tivity, not even high edge-connectivity (examples?).It does, however,imply the existence of a highly connected subgraph:[72]Theorem 1.4.3. (Mader 1972)Let 0 + k e N. Every graph G with d(G) ≥ 4k has a (k+ 1)-connectedsubgraph H such that e(H) > (G) -k
12 1. The Basics If |G| > 1 and G − F is connected for every set F ⊆ E of fewer than edges, then G is called -edge-connected. The greatest integer -edgeconnected such that G is -edge-connected is the edge-connectivity λ(G) of G. In particular, we have λ(G) = 0 if G is disconnected. edgeconnectivity λ(G) G H Fig. 1.4.3. The octahedron G (left) with κ(G) = λ(G) = 4, and a graph H with κ(H)=2 but λ(H)=4 Proposition 1.4.2. If G is non-trivial then κ(G) λ(G) δ(G). Proof . The second inequality follows from the fact that all the edges incident with a fixed vertex separate G. To prove the first, let F be any minimal subset of E such that G − F is disconnected. We show that κ(G) |F|. Suppose first that G has a vertex v that is not incident with an edge in F. Let C be the component of G−F containing v. Then the vertices of C that are incident with an edge in F separate v from G − C. Since no edge in F has both ends in C (by the minimality of F), there are at most |F| such vertices, giving κ(G) |F| as desired. Suppose now that every vertex is incident with an edge in F. Let v be any vertex, and let C be the component of G−F containing v. Then the neighbours w of v with vw /∈ F lie in C and are incident with distinct edges in F, giving dG(v) |F|. As NG(v) separates v from all the other vertices in G, this yields κ(G) |F|—unless there are no other vertices, i.e. unless { v } ∪ N(v) = V . But v was an arbitrary vertex. So we may assume that G is complete, giving κ(G) = λ(G) = |G| − 1. By Proposition 1.4.2, high connectivity requires a large minimum degree. Conversely, large minimum degree does not ensure high connectivity, not even high edge-connectivity (examples?). It does, however, imply the existence of a highly connected subgraph: Theorem 1.4.3. (Mader 1972) [ 7.2.1 ] [ 11.2.3 ] Let 0 = k ∈ N. Every graph G with d(G) 4k has a (k + 1)-connected subgraph H such that ε(H) > ε(G) − k.
131.4 Connectivity13312:1Proof. Put := e(G) (≥ 2k), and consider the subgraphs G' C G suchthatIG'I≥2k and IIG'l >(IG'I-k).(*)Such graphs G' exist since G is one; let H be one of smallest order.HNo graph G' as in (*) can have order exactly 2k, since this wouldimply that G' > k ≥ 2k? > (IC'l). The minimality of H thereforeimplies that (H) > : otherwise we could delete a vertex of degree atmost and obtain a graph G' C H still satisfying (*). In particular, wehave [H] ≥. Dividing the inequality of |HIl >|H] -k from (*) by[H| therefore yields e(H) > - k, as desiredIt remains to show that H is (k + 1)-connected. If not, then H hasa proper separation Ui, U,] of order at most k; put H[Ul =: H,Hi,H2Since any vertex e Ui U, has all its d(v) ≥ (H) > neighboursfrom H in Hi, we have [Hi] ≥≥ 2k. Similarly, [H2] ≥ 2k. As by theminimality of H neither Hi nor H2 satisfies (*), we further haveIH:II≤(H/-k)for i =- 1,2. But thenH≤ IHII+[H2I≤((Hi|+[H2] -2k)≤(H}-)(as |HinH2/ ≤ k)口which contradicts (*) for H1.5 Trees and forestsAn acyclic graph, one not containing any cycles, is called a forest. A con.forestnected forest is called a tree. (Thus, a forest is a graph whose componentstreeare trees.) The vertices of degree 1 in a tree are its leaves.5 Every non-leaftrivial tree has a leaf-consider, for example, the ends of a longest path.This little fact often comes in handy, especially in induction proofs abouttrees: if we remove a leaf from a tree, what remains is still a tree.except that the root ofa tree (see below) is never called a leaf, even if it hasdegree 1
1.4 Connectivity 13 Proof . Put γ := ε(G) ( 2k), and consider the subgraphs G ⊆ G such (1.2.2) (1.3.1) γ that |G | 2k and G > γ |G | − k . (∗) Such graphs G exist since G is one; let H be one of smallest order. H No graph G as in (∗) can have order exactly 2k, since this would imply that G > γk 2k2 > |G | 2 . The minimality of H therefore implies that δ(H) > γ : otherwise we could delete a vertex of degree at most γ and obtain a graph G H still satisfying (∗). In particular, we have |H| γ. Dividing the inequality of H > γ |H| − γk from (∗) by |H| therefore yields ε(H) > γ − k, as desired. It remains to show that H is (k + 1)-connected. If not, then H has a proper separation {U1, U2 } of order at most k; put H [Ui ] =: Hi. H1, H2 Since any vertex v ∈ U1 U2 has all its d(v) δ(H) > γ neighbours from H in H1, we have |H1| γ 2k. Similarly, |H2| 2k. As by the minimality of H neither H1 nor H2 satisfies (∗), we further have Hi γ |Hi| − k for i = 1, 2. But then H H1 + H2 γ |H1| + |H2| − 2k γ |H| − k (as |H1 ∩ H2| k), which contradicts (∗) for H. 1.5 Trees and forests An acyclic graph, one not containing any cycles, is called a forest. A con- forest nected forest is called a tree. (Thus, a forest is a graph whose components tree are trees.) The vertices of degree 1 in a tree are its leaves. 5 Every non- leaf trivial tree has a leaf—consider, for example, the ends of a longest path. This little fact often comes in handy, especially in induction proofs about trees: if we remove a leaf from a tree, what remains is still a tree. 5 ... except that the root of a tree (see below) is never called a leaf, even if it has degree 1.
141.The BasicsFig. 1.5.1.A tree[180]Theorem 1.5.1. The following assertions are equivalent for a graph T:[4.2.9](i) T is a tree;(i) Any two vertices of T are linked by a unique path in T:(ii) T is minimally connected, i.e. T is connected but T-e is discon-nected for every edge e e T;(iv) T is maximally acyclic, i.e. T contains no cycle but T+ ry does.口for any two non-adjacent vertices a, y e T.The proof of Theorem 1.5.1 is straightforward, and a good exercisefor anyone not yet familiar with all the notions it relates,Extending ournotation for paths from Section 1.3, we write rTy for the unique pathrTyin a tree T between two vertices z,y (see (i) above).A frequently used application of Theorem 1.5.1 is that every con-nected graph contains a spanning tree: by the equivalence of (i) and (ii)any minimal connected spanning subgraph will be a tree. Figure 1.4.1shows a spanning tree in each of the three components of the graphdepicted.Corollary 1.5.2. The vertices of a tree can always be enumerated, sayas Vi,...,Un, so that every vi with i ≥ 2 has a unique neighbour in[u.....Ui--].口(1.4.1)Proof. Use the enumeration from Proposition 1.4.1.[2.9.0]Corollary 1.5.3. A connected graph with n vertices is a tree if and[2.4.4]only if it has n-1 edges.[4.2.9]Proof. Induction on shows that the subgraph spanned by the firsti vertices in Corollary 1.5.2 has i-1 edges; for i = n this proves theforward implication.Conversely, let G be any connected graph with nvertices and n -1 edges. Let G' be a spanning tree in G. Since G' hasn -1 edges by the first implication, it follows that G = G'.口
14 1. The Basics Fig. 1.5.1. A tree Theorem 1.5.1. The following assertions are equivalent for a graph T: [ 1.6.1 ] [ 1.9.6 ] [ 4.2.9 ] (i) T is a tree; (ii) Any two vertices of T are linked by a unique path in T; (iii) T is minimally connected, i.e. T is connected but T − e is disconnected for every edge e ∈ T; (iv) T is maximally acyclic, i.e. T contains no cycle but T + xy does, for any two non-adjacent vertices x, y ∈ T. The proof of Theorem 1.5.1 is straightforward, and a good exercise for anyone not yet familiar with all the notions it relates. Extending our xT y notation for paths from Section 1.3, we write xT y for the unique path in a tree T between two vertices x, y (see (ii) above). A frequently used application of Theorem 1.5.1 is that every connected graph contains a spanning tree: by the equivalence of (i) and (iii), any minimal connected spanning subgraph will be a tree. Figure 1.4.1 shows a spanning tree in each of the three components of the graph depicted. Corollary 1.5.2. The vertices of a tree can always be enumerated, say as v1,...,vn, so that every vi with i 2 has a unique neighbour in { v1,...,vi−1 }. (1.4.1) Proof . Use the enumeration from Proposition 1.4.1. Corollary 1.5.3. A connected graph with n vertices is a tree if and [ 1.9.6 ] [ 2.4.1 ] [ 2.4.4 ] [ 4.2.9 ] only if it has n − 1 edges. Proof . Induction on i shows that the subgraph spanned by the first i vertices in Corollary 1.5.2 has i − 1 edges; for i = n this proves the forward implication. Conversely, let G be any connected graph with n vertices and n − 1 edges. Let G be a spanning tree in G. Since G has n − 1 edges by the first implication, it follows that G = G .