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 max￾imum 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: