61.The BasicsIf a graph has large minimum degree, ie. everywhere, locally, manyedges 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 minimum degree is small. However, the vertices of largedegree cannot be scattered completely among vertices of small degree: asthe next proposition shows, every graph G has a subgraph whose averagedegree is no less than the average degree of G, and whose minimumdegree is more than half its average degree:1.4.3]Proposition 1.2.2. Every graph G with at least one edge has a sub-[3.5.1]graph 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(u) can we afford to delete a vertex v, without lowering e?Clearly, up to d(v) = e: then the number of vertices decreases by 1and the number of edges by at most e, so the overall ratio e of edges toverticeswillnotdecreaseFormally, we construct a sequence G - Go 2 Gi 2... of inducedsubgraphs of G as follows. If G, has a vertex u; of degree d(u:) ≤ e(G),G, -w; if not, we terminate our sequence and setletGi+H := Gf. 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(K1) = 0 < e(G),none of the graphs in our sequence is trivial, so in particular H + 0. Thefact that H has no vertex suitable for deletion thus implies d(H) > e(H),as claimed.口1.3 Paths and cyclespathA path is a non-empty graph P = (V,E) of the formV= [,. ]E-ao,2,..,k-ak],where the ri are all distinct. The vertices ro and k are linked by P andare called its ends; the vertices T1,.., rk-1 are the inner vertices of P.lengthThe number of edges of a path is its length, and the path of length k ispkdenoted by Pk. Note that k is allowed to be zero; thus, po -KiWe often refer to a path by the natural sequence of its vertices,3writing, say, P = rori...k and calling P a path from ro to rk (as wellas between To and rk)3 More precisely.by one of the two natural sequences:zo...k and rkgs of V(P)denote the same path.Still.it often helps to fix one of these two orderinotationally: we may then speak of things like the first'vertex on P with a certainproperty,etc6 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 ] [ 3.5.1 ] 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 ends; the vertices x1,...,xk−1 are the inner vertices of P. length The number of edges of a path is its length, and the path of length k is denoted by Pk. Note that k is allowed to be zero; thus, P0 = K1 P . k We often refer to a path by the natural sequence of its vertices,3 writing, say, P = x0x1 ...xk and calling P a path from x0 to xk (as well as between x0 and xk). 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.