1. The BasicsIf p = To... Tk-1 is a path and k ≥ 3, then the graph C :=cycleP+Tk-o is called a cucle.As with paths.we often denote a cvcleby its (cyclic) sequence of vertices; the above cycle C might be writtenlengthro.The lengthofa cycleisitsnumberofedges (orvertices);tthe cycle of length k is called a k-cycle and denoted by CkCThe minimum length of a cycle (contained)in a graph G is the girt)girth g(G)g(G) of G; the maximum length of a cycle in G is its circumnce.(IfG does not contain a cycle, we set the former to oo, the latter to zero.)chordAn edge which joins two vertices of a cycle but is not itself an edge ofthe cycle is a chord of that cycle. Thus, an induced cycle in G, a cycle in inducedG forming an induced subgraph, is one that has no chords (Fig. 1.3.3).cycleFig. 1.3.3. A cycle C8 with chord ry, and induced cycles C6,c4If a graph has large minimum degree, it contains long paths andcycles (see also Exercise 9):1.4Proposition 1.3.1. Every graph G contains a path of length (G) anda cycle of length at least 8(G) +1 (provided that (G) ≥ 2)Proof. Let rost path in G. Then all the neighbours ofTbealongesTk lie on this path (Fig. 1.3.4). Hence k ≥ d(rk) ≥ s(G). If i < k ismal with irk e E(G), then ai... Tki is a cycle of length at least8(G) + 1.口roFig. 1.3.4. A longest path ro... re, and the neighbours of rMinimum degree and girth, on the other hand, are not related (un-less we fix the number of vertices): as we shall see in Chapter 1l, thereare graphs combining arbitrarily large minimum degree with arbitrarilylarge girth.distanceThe distance dc(,y) in G of two vertices a,y is the length of ad(a,y)shortest T-y path in G: if no such path exists, we set d(r, y) := oo. Thegreatest distance between any two vertices in G is the diameter of G,denoted by diam(G). Diameter and girth are, of course, related:diam(G)
8 1. The Basics If P = x0 ...xk−1 is a path and k 3, then the graph C := cycle P + xk−1x0 is called a cycle. As with paths, we often denote a cycle by its (cyclic) sequence of vertices; the above cycle C might be written length as x0 ...xk−1x0. The length of a cycle is its number of edges (or vertices); the cycle of length k is called a k-cycle and denoted by Ck C . k girth g(G) The minimum length of a cycle (contained) in a graph G is the girth g(G) of G; the maximum length of a cycle in G is its circumference. (If circumference G does not contain a cycle, we set the former to ∞, the latter to zero.) chord An edge which joins two vertices of a cycle but is not itself an edge of the cycle is a chord of that cycle. Thus, an induced cycle in G, a cycle in G forming an induced subgraph, is one that has no chords (Fig. 1.3.3). induced cycle y x Fig. 1.3.3. A cycle C8 with chord xy, and induced cycles C6, C4 If a graph has large minimum degree, it contains long paths and cycles (see also Exercise 9): Proposition 1.3.1. Every graph G contains a path of length δ(G) and [1.4.3] [7.2.2] a cycle of length at least δ(G)+1 (provided that δ(G) 2). Proof. Let x0 ...xk be a longest path in G. Then all the neighbours of xk lie on this path (Fig. 1.3.4). Hence k d(xk) δ(G). If i<k is minimal with xixk ∈ E(G), then xi ...xkxi is a cycle of length at least δ(G) + 1. x0 xi xk Fig. 1.3.4. A longest path x0 ...xk, and the neighbours of xk Minimum degree and girth, on the other hand, are not related (unless we fix the number of vertices): as we shall see in Chapter 11, there are graphs combining arbitrarily large minimum degree with arbitrarily large girth. The distance dG(x, y) in G of two vertices x, y is the length of a distance d(x, y) shortest x–y path in G; if no such path exists, we set d(x, y) := ∞. The greatest distance between any two vertices in G is the diameter of G, denoted by diam(G). Diameter and girth are, of course, related: diameter diam(G)
1.3 Paths and cycles9Proption 1.3.2. Every graph G containing a cycle satisfies g(G) ≤2 diam(G) + 1.Proof Let C be a shortest cvcle in G. If g(G) ≥2diam(G) +2: thenC has two vertices whose distance in C is at least diam(G) +1. In G,these vertices have a lesser distance; any shortest path P between themis therefore not a subgraph of C.Thus, P contains a C-path rPy.Together with the shorter of the two -y paths in C, this path rPyforms a shorter cycle than C, a contradiction广A vertex is central in G if its greatest distance from any other ver-centraltex is as small as possible. This distance is the radius of G, denotedmaleby rad(G). Thus, formally, rad(G) = minev(C) maxyev(G) de(r,y)As one easily checks (exercise), we haverad(G)≤diam(G)≤2rad(G)Diameter and radius are not related to minimum, average or maximum degree if we say nothing about the order of the graph. Howevergraphs of large diameter and minimum degree must be large (larger thanforced by each of the two parameters alone; see Exercise 10), and graphsof small diameter and maximum degree must be small841Proposition 1.3.3. A graph G of radius at most k and maximum degreeat most d ≥3 has fewer than (d-1)* verticesProof. Let z be a central vertex in G, and let D, denote the set of verticeof G at distance i from z. Then V(G) = U'=o D,. Clearly [Dol = 1 and[D]< d. For i>1 we have [D+1l< (d-1]Dl, because every vertexin Di+1 is a neighbour of a vertex in D, (why?), and each vertex in Dhas at most d -1 neighbours in Di+1 (since it has another neighbouin Di-1). Thus |Di+il ≤ d(d-1) for all i < k by induction, givingG]≤1+2(d-1)=+(d-1)-1) <a-2(d-1)1=0口milarly, we can bound the order of G from below by assuming thatboth its minimum degree and girth are large. For d e R and g e N let1+d(d-1)if g =: 2r +1 is odd:1=0no(d,g) :2 (d-1)if g =: 2r is even.i=0
1.3 Paths and cycles 9 Proposition 1.3.2. Every graph G containing a cycle satisfies g(G) 2 diam(G)+1. Proof. Let C be a shortest cycle in G. If g(G) 2 diam(G) + 2, then C has two vertices whose distance in C is at least diam(G) + 1. In G, these vertices have a lesser distance; any shortest path P between them is therefore not a subgraph of C. Thus, P contains a C-path xP y. Together with the shorter of the two x–y paths in C, this path xP y forms a shorter cycle than C, a contradiction. A vertex is central in G if its greatest distance from any other ver- central tex is as small as possible. This distance is the radius of G, denoted by rad(G). Thus, formally, rad(G) = minx∈V (G) maxy∈V (G) dG(x, y). radius rad(G) As one easily checks (exercise), we have rad(G) diam(G) 2 rad(G). Diameter and radius are not related to minimum, average or maximum degree if we say nothing about the order of the graph. However, graphs of large diameter and minimum degree must be large (larger than forced by each of the two parameters alone; see Exercise 10), and graphs of small diameter and maximum degree must be small: Proposition 1.3.3. A graph G of radius at most k and maximum degree [9.4.1] [9.4.2] at most d 3 has fewer than d d−2 (d − 1)k vertices. Proof. Let z be a central vertex in G, and let Di denote the set of vertices of G at distance i from z. Then V (G) = k i=0 Di. Clearly |D0| = 1 and |D1| d. For i 1 we have |Di+1| (d − 1)|Di|, because every vertex in Di+1 is a neighbour of a vertex in Di (why?), and each vertex in Di has at most d − 1 neighbours in Di+1 (since it has another neighbour in Di−1). Thus |Di+1| d(d − 1)i for all i<k by induction, giving |G| 1 + d k −1 i=0 (d − 1)i = 1+ d d − 2 (d − 1)k − 1 < d d − 2 (d − 1)k. Similarly, we can bound the order of G from below by assuming that both its minimum degree and girth are large. For d ∈ R and g ∈ N let n0(d, g) := ⎧ ⎪⎪⎪⎪⎪⎨ ⎪⎪⎪⎪⎪⎩ 1 + d r−1 i=0 (d − 1)i if g =: 2r + 1 is odd; 2 r−1 i=0 (d − 1)i if g =: 2r is even.
101. The BasicsIt isnotdifficulttoprovethatagraphofmum degree and girth ghas at least no(o,g) vertices (Exercise 7). Interestingly, one can obtainthe same bound for its average degree:Theorem 1.3.4. (Alon, Hoory & Linial 2002)Let G be a graph. If d(G) ≥ d ≥ 2 and g(G) ≥ g e N then JGI ≥ no(d, g)One aspect of Theorem 1.3.4 is that it guarantees the existence ofa short cycle compared with JGj. Using just the easy minimum degreeversion of Exercise 7, we get the following rather general bound:Corollary 1.3.5. If 8(G) ≥3 then g(G) < 2log/GJ.[2.3.1]Proof. If g := g(G) is even then29/2 1= 29/2 +(29/2 ~2) > 29/2,no(3, g) = 2-1while if g is odd then2(g-1)/2 _129/2=2>29/2no(3, g) = 1 +32-1V2As |G| ≥ no(3, g), the result follows.口walkAwalk(of lengthk)inagraphGisanon-emptyalternatingsequence voeouie1..ek-iuk of vertices and edges in G such that e. -[vi, vi+i] for all i < k. If vo =- vk, 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 ConnectivityAgraph Gis called connected ifitinotI-empty and any two of itsconnectedvertices are linked by a path in G. If U c V(G) and G[U] is connected,we also call U itself connected (in G).Instead of not connected'weusuallysaydisconnected[1.5.2]Proposition 1.4.1. The vertices of a connected graph G can always beumerated, say as v,.,'n, so that G, := Glu..,u] is connectedfor every i.weshalofenusetermsdefnedforgaphsalsoforwalks,aslongastheirmeaning is obvious
10 1. The Basics It is not difficult to prove that a graph of minimum degree δ and girth g has at least n0(δ, g) vertices (Exercise 7). Interestingly, one can obtain the same bound for its average degree: 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 7, 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 graph G is called connected if it is non-empty and 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. 4 We shall often use terms defined for graphs also for walks, as long as their meaning is obvious.
111.4 ConnectivityProof.Pickand assume inductively that i,..., u, haveyverbeen chosen for some i < |Gj. Now pick a vertex e G- Gi. As G isconnected, it contains a w-u1 path P. Choose as vi+1 the last vertex ofP in G- Gi; then vi+1 has a neighbour in Gi. The connectedness ofevery G, follows by induction on i.LLet G = (V,E) be a graph. A maximal connected subgraph of G isa component of G. Clearly, the components are induced subgraphs, andcomponenttheir vertex sets partition V.Since connected graphs are non-empty, theemptygraphhas no componentsFig. 1.4.1. A graph with three components, and a minimalspanningconnectedsubgraphineachcomponentIf A,B C V and X VUE 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 X. We say that X separatestwo vertices a,b if it separates the sets [a], (b] but a,b X, and that Xseparates G if X separates some two vertices in G. A separating set ofvertices is a sepgrator.Separating sets of edges have no geneseparatorbut some suchsets do; see Section 1.9 for the definition of cuts and bonds.A vertex which separates two other vertices of the same component is acutvertexcutuerter, and an edge separating its ends is a bridge. Thus, the bridgesbridgein a graph are precisely those edges that do not lie on any cycle.XXFig. 1.4.2. A graph with cutvertices u, ,y, w and bridge e = rThe unordered pair [A, B] is a separation of G if AUB = V and Gseparationhas no edge between A<B and B~A. Clearly, the latter is equivalentto saying that AnB separates A from B. If both A\B and BA arenon-empty, the sepration is proper. The number [AnB is the order ofthe sepaation [A, B]: the sets A, B are its sidesGis called k-connected (forkeN)if|GI>k and G-X isconnected k-connectedfor every set X V with [X < k. In other words, no two vertices of G
1.4 Connectivity 11 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. Let G = (V,E) be a graph. A maximal connected subgraph of G is a component of G. Clearly, the components are induced subgraphs, and component their vertex sets partition V . Since connected graphs are non-empty, the empty graph 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. We say that X separates two vertices a, b if it separates the sets {a}, {b} but a, b /∈ X, and that X separates G if X separates some two vertices in G. A separating set of vertices is a separator. Separating sets of edges have no generic name, separator but some such sets do; see Section 1.9 for the definition of cuts and bonds. A vertex which separates two other vertices of the same component is a cutvertex cutvertex, and an edge separating its ends is a bridge. Thus, the bridges bridge in a graph 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}; the sets A, B are its sides. 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
121. The Basicsare separated by fewer than k other vertices. Every (non-empty) graphis 0-connected. and the 1-connected graphs are precisely the non-trivialconnected graphs. The greatest integer k such that G is k-connectedmnectivity isthetonnectivity (G) of G.Thus, k(C) Oifand only ifGisK(G)disconnected or a K', and k(K") = n -1 for all n ≥ 1If [GI > 1 and G - F is set FC E of fewelectedforevCealetedthan l edges, then G is called l-edge-connected. The greatest integer lsuch that G is l-edge-connected is the edge-connectivity A(G) of G. Inedge-ectivity particular,we have (G)=O if G is disconnected入(G)Fig. 1.4.3. The octahedron G (left) with k(G) = A(G) = 4and a graph H with x(H) = 2 but (H) =4[3.2.1]Proposition 1.4.2.IfG is non-trivial then k(G)≤>(G)≤o(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 aset of X(G) edges such that G- F is disconnected. Such a set exists bydefinition of X; note that F is a minimal separating set of edges in G.Weshowthatk(G)<Fpose first that G has a vertex y that is not incident with an edgeS11TinFLetCbetheiponent of G-F containing y. Then the verticesof C that arincident with an edge in F separate frnG-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 ube any vertex, and let C be the component of G-F containing v. Thenthe neighbours w of u with ww F lie in C and are incident with distinctimality of F), giving dc(o) ≤ [F]. Asedges in F (again bythe miniNc(u) separates from any other vertices in G, this yields k(G) ≤ |F|unless there are no other vertices, ie. unless (ujUN(u) - V.Butuwas an arbitrary vertex.So wemay assume that Gis complete,givingk(G) = ^(G) = [G|- 1.By Proposition 1.4.2, high connectivity requires a large minimumdegree. 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:
12 1. The Basics 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. 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 [3.2.1] 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 a set of λ(G) edges such that G − F is disconnected. Such a set exists by definition of λ; note that F is a minimal separating set of edges in G. 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 (again by the minimality of F), giving dG(v) |F|. As NG(v) separates v from any 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: