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 circum￾ference 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 (un￾less 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)