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 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 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 (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 Proposition 1.3.2. Every graph G containing a cycle satisfies g(G) 2 diam G + 1.