51.2 The degree of a vertex1.2 The degree of a vertexLet G = (V,E) be a (non-empty) graph. The set of neighbours of avertex u in G is denoted by Nc(u), or briefly by N(u).1 More generallyN(u)for U , the neighbours in VU of vertices in U are called neighboursof U; their set is denoted by N(U).The degree (or walency) de(u) = d(u) of a vertex y is the numberdegree d(u)[E(u)/ of edges at v; by our definition of a graph,? this is equal to thenumber of neighbours of v. A vertex of degree O is isolated. The number isolated(G) := min [ d(u) I u e V) is the minimum degree of G, the number5(G)A(G) := max (d(o) I e V) its marimum degree. If all the vertices△(G) of G have the same degree k, then G is k-regular, or simply regular. Aregular3-regular graph is called cubic.cubicThe number1d(u)d(G) :=VIEVa(G)areis the average degree of G. Clearly,8(G) ≤ d(G) ≤△(G) .The average degree quantifies globally what is measured locally by thevertex degrees: the number of edges of G per vertex. Sometimes it willbe convenient to express this ratio directly, as e(G) := [E|/lV)e(G)The quantities d and e are, of course, intimately related. Indeed,if we sum up all the vertex degrees in G, we count every edge exactlytwice:oncefrom each of its ends. Thus[E=d() = d(G):IVI,VEVand thereforee(G) = d(G).Proposition 1.2.1. The number of vertices of odd degree in a graph is[10.3.3]always evenProof. A graph on V has Euevd(u) edges, so Ed(o) is an even口number.Hereaselsewhre, wedohindxrringothunderlnggraphireferenceisclear2but not for multigraphs; see Section 1.10
1.2 The degree of a vertex 5 1.2 The degree of a vertex Let G = (V,E) be a (non-empty) graph. The set of neighbours of a vertex v in G is denoted by NG(v), or briefly by N(v).1 More generally N(v) for U ⊆ V , the neighbours in V U of vertices in U are called neighbours of U; their set is denoted by N(U). The degree (or valency) dG(v) = d(v) ofavertex v is the number degree d(v) |E(v)| of edges at v; by our definition of a graph,2 this is equal to the number of neighbours of v. A vertex of degree 0 is isolated. The number isolated δ(G) := min { d(v) | v ∈ V } is the minimum degree of G, the number δ(G) ∆(G) := max { d(v) | v ∈ V } its maximum degree. If all the vertices ∆(G) of G have the same degree k, then G is k-regular , or simply regular . A regular 3-regular graph is called cubic. cubic The number d(G) := 1 |V | v∈V d(v) d(G) is the average degree of G. Clearly, average degree δ(G) d(G) ∆(G). The average degree quantifies globally what is measured locally by the vertex degrees: the number of edges of G per vertex. Sometimes it will be convenient to express this ratio directly, as ε(G) := |E|/|V |. ε(G) The quantities d and ε are, of course, intimately related. Indeed, if we sum up all the vertex degrees in G, we count every edge exactly twice: once from each of its ends. Thus |E| = 1 2 v∈V d(v) = 1 2 d(G)· |V | , and therefore ε(G) = 1 2 d(G). Proposition 1.2.1. The number of vertices of odd degree in a graph is [ 10.3.3 ] always even. Proof . A graph on V has 1 2 v∈V d(v) edges, so d(v) is an even number. 1 Here, as elsewhere, we drop the index referring to the underlying graph if the reference is clear. 2 but not for multigraphs; see Section 1.10
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,etc
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 ] [ 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.
71.3 Paths and cyclesFig.1.3.1.ApathP=P6inGFor 0≤i<j≤ k we writeaPy,pPr,- ro....iaP:-ri..akaiPr, =Ti..tjandP:= T1...Tk-1Pa,.-o...T-1,P:=T+.Tki,Pi, =a+j-1for the appropriate subpaths of P. We use similar intuitive notation forthe concatenation of paths; for example, if the union PrUrQyUyR ofthree paths is again a path, we may simply denote it by PrQyR.PrQyRFig. 1.3.2. Paths P, Q and rPyQzGiven sets A, B of vertices, we call P = Zo...Tk an A-B path ifA-B pathV(P)nA = (ro} and V(P)n B = (]. As before, we write a-Binde-path rather than (a)-B path, etc. Two or more paths are independentpendentif none of them contains an inner vertex of another: Two a-b paths, forinstance, are independent if and only if a and b are their only commonvertices.Given a graph H, we call P an H-path if P is non-trivial and meetsH-pathH exactly in its ends. In particular, the edge of any H-path of length 1is never an edge of H.IfP= ro..Ck-1 is a path and k ≥ 3, then the graph C :P+ k-1to is called a cycle. As with paths, we often denote a cyclecycleby its (cyclic) sequence of vertices; the above cycle C might be written
1.3 Paths and cycles 7 G P Fig. 1.3.1. A path P = P6 in G For 0 i j k we write xP y, P ˚ P xi := x0 ...xi xiP := xi ...xk xiP xj := xi ...xj and P ˚ := x1 ...xk−1 P˚xi := x0 ...xi−1 ˚xiP := xi+1 ...xk ˚xiP˚xj := xi+1 ...xj−1 for the appropriate subpaths of P. We use similar intuitive notation for the concatenation of paths; for example, if the union P x ∪ xQy ∪ yR of three paths is again a path, we may simply denote it by PxQyR. PxQyR x xP yQz y z x P y Q z Fig. 1.3.2. Paths P, Q and xP yQz Given sets A, B of vertices, we call P = x0 ...xk an A–B path if A–B path V (P) ∩ A = { x0 } and V (P) ∩ B = { xk }. As before, we write a–B path rather than { a }–B path, etc. Two or more paths are independent independent if none of them contains an inner vertex of another. Two a–b paths, for instance, are independent if and only if a and b are their only common vertices. Given a graph H, we call P an H-path if P is non-trivial and meets H-path H exactly in its ends. In particular, the edge of any H-path of length 1 is never an edge of H. If P = x0 ...xk−1 is a path and k 3, then the graph C := P + xk−1x0 is called a cycle. As with paths, we often denote a cycle cycle by its (cyclic) sequence of vertices; the above cycle C might be written
81.The Basicslengthas ro ... k-1ro. The length of a cycle is its number of edges (or vertices);ckthe cycle of length k is called a k-cycle and denoted by CkThe minimum length of a cycle (contained) in a graph G is the girthgirth g(G)g(G) of G; the maximum length of a cycle in G is its circumference. (fareneG does not contain a cycle, we set the former to co, the latter to zero.)An edge which joins two vertices of a cycle but is not itself an edge ofchordthe cycle is a chord of that cycle. Thus, an induced cycle in G, a cycle ininducedG forming an induced subgraph, is one that has no chords (Fig. i.3.3).cycleFig. 1.3.3. A cycle C with chord ry, and induced cycles Ce4If a graph has large minimum degree, it contains long paths andcycles (see also Exercise 7):[4.1]Proposition 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 ro ... k be a longest path in G. Then all the neighbours ofk lie on this path (Fig. 1.3.4). Hence k ≥ d(rn) ≥ 6(G). If i<k isminimal with ritk e E(G), then Ti...Ekz, is a cycle of length at least(G) +1.roFig. 1.3.4. A longest path ao...rk, and the neighbours of rkMinimum degree and girth, on the other hand, are not related (un-less we fix the number of vertices): as we shall see in Chapter ll, thereare graphs combining arbitrarily large minimum degree with arbitrarilylarge girth.distanceThe distance dc(r,y) in G of two vertices ,y is the length of ad(r,y)shortest -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,diameterdenoted by diam G. Diameter and girth are, of course, related:diamGProposition 1.3.2. Every graph G containing a cycle satisfies g(G) ≤2diamG+1
8 1. The Basics 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 7): Proposition 1.3.1. Every graph G contains a path of length δ(G) and [ 1.4.3 ] [ 3.5.1 ] 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 Proposition 1.3.2. Every graph G containing a cycle satisfies g(G) 2 diam G + 1.
91.3 Paths and cyclesProof. Let C be a shortest cycle in G. If g(G) ≥ 2diamG + 2, thenC has two vertices whose distance in C is at least diamG +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 rPyTogether 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 Gifits greatest distance from any other vertexcentralis as small as possible. This distance is the radius of G, denoted by rad G.radiusThus, fomally, rad =minev( maxye() dc(,) As one easilyradGchecks (exercise), we haveradG≤diamG2radGDiameter and radius are not related to minimum, average or max-imum degree if we say nothing about the order of the graph. However.graphs of large diameter and minimum degree are clearly large (muchlarger than forced by each of the two parameters alone; see Exercise 8),and graphs of small diameter and maximum degree must be small:[8.42]Proposition 1.3.3. A graph G of radius at most k and maximum degreeat most d ≥ 3 has fewer than ,(d - 1)* vertices.Proof. Let z be a central vertex in G, and let D; denote the set ofvertices of G at distance i from z. Then V(G) = U'=o D, Clearly[Dol = 1 and [D;] ≤ d. For i≥1 we have [Di+1/ ≤ (d-i)][D-l, becauseevery vertex in Di+i is a neighbour of a vertex in D, and each vertex inD, has at most d-1 neighbours in Di+1 (since it has another neighbourin Di-1). Thus [Di+il d(d-1) for all i< k by induction, giving2-dIl≤1+d(α-1) =1+-,(d-1)-1) <,(a-1),1=0ASimilarly, 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;=0no(d,.g) :-2(d-1)iif g =: 2r is even.It is not dificult to prove that a graph of minimum degree and girth ghas at least no(3,g) vertices (Exercise 6). Interestingly, one can obtainthe same bound for its average degree:
1.3 Paths and cycles 9 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 vertex central 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). As one easily radius rad G 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 are clearly large (much larger than forced by each of the two parameters alone; see Exercise 8), 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, 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. It is not difficult to prove that a graph of minimum degree δ and girth g has at least n0(δ, g) vertices (Exercise 6). Interestingly, one can obtain the same bound for its average degree: