61. The BasicIfa graph has largeminimum degree.i.e.evervwhere.locally.manvedges per vertex, it also has many edges per vertex globally: e(G) d(G) ≥ o(G). Conversely, of course, its average degree may be largeeven when its miinimumdegreeissmall.However,theverticesoflargedegree cannot be scattered completely among vertices of small degree: asthe next proposition shows, every graph G has a subgraph whose avelragedegree is no less than the average degree of G, and whose minimundegree is more than half its average degree1.2Pro122FhGwithatlehas a subioroneedgegraph H with (H)>e(H)≥e(G)Proof. To construct H from G, let us try to delete vertices of smalldegree one by one, until only vertices of large degree remain. Up towhich degree d(v) can we afford to delete a vertex v, without lowering e?Clearly, up to d(u) = e: then the number of vertices decreases by 1and the number of edges by at most e, so the overall ratio e of edges tovertices will not decreasFormally, we construct a sequence G = Go 2 Gi 2 ... of inducedsubgraphs of G as follows. If G, has a vertex v; of degree d(v:) ≤ e(G)reletGiG,-v:if notweterminate ouH := G, By the choices of u; we have e(Gi+1) ≥ e(G) for all i, andhence e(H) ≥ e(G).What else can we say about the graph H? Since e(K') = 0 < e(G)none of the graphs in our sequenceistrivial,soinparticularH+.Thefact that H has no vertex suitable for deletion thus implies (H) > e(H)as claimed.1.3 Paths and cyclesA path is a non-empty graph P.= (V,E) of the formpathV= [1o, T1,...,]E = [ror1,ri2,*,k-1k],where the r, are all distinct. The vertices To and rk are linked by P andare called its endvertices or ends; the vertices Ti,.., k-1 are the innervertices of P.The numberofedges of a path is its length, and the pathlengthpkof length k is denoted by Pk. Note that k is allowed to be zero; thus,00一KWe often refer to a path by the natural sequence of its vertices,3MorepiselybyeofthwonaturalsqunkandVdenotetnhelpstofixitoproperty, ete.6 1. The Basics If a graph has large minimum degree, i.e. everywhere, locally, many edges per vertex, it also has many edges per vertex globally: ε(G) = 1 2 d(G)  1 2 δ(G). Conversely, of course, its average degree may be large even when its minimum degree is small. However, the vertices of large degree cannot be scattered completely among vertices of small degree: as the next proposition shows, every graph G has a subgraph whose average degree is no less than the average degree of G, and whose minimum degree is more than half its average degree: Proposition 1.2.2. Every graph G with at least one edge has a sub- [1.4.3] [7.2.2] graph H with δ(H) > ε(H)  ε(G). Proof. To construct H from G, let us try to delete vertices of small degree one by one, until only vertices of large degree remain. Up to which degree d(v) can we afford to delete a vertex v, without lowering ε? Clearly, up to d(v) = ε : then the number of vertices decreases by 1 and the number of edges by at most ε, so the overall ratio ε of edges to vertices will not decrease. Formally, we construct a sequence G = G0 ⊇ G1 ⊇ ... of induced subgraphs of G as follows. If Gi has a vertex vi of degree d(vi) ε(Gi), we let Gi+1 := Gi − vi; if not, we terminate our sequence and set H := Gi. By the choices of vi we have ε(Gi+1)  ε(Gi) for all i, and hence ε(H)  ε(G). What else can we say about the graph H? Since ε(K1)=0 < ε(G), none of the graphs in our sequence is trivial, so in particular H = ∅. The fact that H has no vertex suitable for deletion thus implies δ(H) > ε(H), as claimed. 1.3 Paths and cycles path A path is a non-empty graph P = (V,E) of the form V = {x0, x1,...,xk} E = {x0x1, x1x2,...,xk−1xk} , where the xi are all distinct. The vertices x0 and xk are linked by P and are called its endvertices or ends; the vertices x1,...,xk−1 are the inner length vertices of P. The number of edges of a path is its length, and the path of length k is denoted by Pk P . Note that k is allowed to be zero; thus, k P0 = K1. We often refer to a path by the natural sequence of its vertices,3 3 More precisely, by one of the two natural sequences: x0 ...xk and xk ...x0 denote the same path. Still, it often helps to fix one of these two orderings of V (P) notationally: we may then speak of things like the ‘first’ vertex on P with a certain property, etc.