101.The BasicsTheorem 1.3.4. (Alon, Hoory & Linial 2002)Let G be a graph. If d(G) ≥ d ≥ 2 and g(G) ≥ g e N then [G| ≥ no(d, g)One aspect of Theorem 1.3.4 is that it guarantees the existence ofa short cycle compared with |Gj. Using just the easy minimum degreeversion of Exercise 6, we get the following rather general bound:[2.3.1]Corollary 1.3.5. If 8(G) ≥ 3 then g(G) < 2log /G)Proof. If g := g(G) is even then29/21= 29/2 + (29/2 = 2) > 29/2,no(3, 9) = 22-1while if g is odd then2(g-1)/2 1329/2-2>29/2.no(3,g)=1+32-1V2口As G[ ≥ no(3, g), the result follows.A walk (of length k) in a graph G is a non-empty alternating se-walkquence Voeouiei...ek-iuk of vertices and edges in G such that e, -ui, Ui+1] for all i<k. If vo = vs, the walk is closed. If the verticesin a walk are all distinct, it defines an obvious path in G. In general,every walk between two vertices contains a path between these vertices(proof?).1.4 ConnectivityconnectedA non-empty graph G is called connected if any two of its vertices arelinked by a path in G. If U C V(G) and G[U] is connected, we alsocall U itself connected (in G). Instead of 'not connected' we usually say'disconnected'.[1.5.2]Proposition 1.4.1. The vertices of a connected graph G can always beenumerated, say as vi,..., Un, so that G, : G[vi,..., u,] is connectedfor everyiProof. Pick any vertex as vi, and :assume inductively that i,..,have been chosen for some i< JGJ. Now pick a vertex u e G- G,. As Gis connected, it contains a v-ui path P. Choose as ui+1 the last vertexof P in G-G; then Ui+i has a neighbour in G,. The connectedness of口every G, follows by induction on i.4Weshalloften use terms defined for graphs also for walks, as long as theirmeaning is obvious.10 1. The Basics Theorem 1.3.4. (Alon, Hoory & Linial 2002) Let G be a graph. If d(G) d 2 and g(G) g ∈ N then |G| n0(d, g). One aspect of Theorem 1.3.4 is that it guarantees the existence of a short cycle compared with |G|. Using just the easy minimum degree version of Exercise 6, we get the following rather general bound: [ 2.3.1 ] Corollary 1.3.5. If δ(G) 3 then g(G) < 2 log |G|. Proof . If g := g(G) is even then n0(3, g)=2 2g/2 − 1 2 − 1 = 2g/2 + (2g/2 − 2) > 2g/2, while if g is odd then n0(3, g) = 1+3 2(g−1)/2 − 1 2 − 1 = 3 √2 2g/2 − 2 > 2g/2. As |G| n0(3, g), the result follows.
walk A walk (of length k) in a graph G is a non-empty alternating se￾quence v0e0v1e1 ...ek−1vk of vertices and edges in G such that ei = { vi, vi+1 } for all i<k. If v0 = vk, the walk is closed. If the vertices in a walk are all distinct, it defines an obvious path in G. In general, every walk between two vertices contains4 a path between these vertices (proof?). 1.4 Connectivity connected A non-empty graph G is called connected if any two of its vertices are linked by a path in G. If U ⊆ V (G) and G [U ] is connected, we also call U itself connected (in G). Instead of ‘not connected’ we usually say ‘disconnected’. [ 1.5.2 ] Proposition 1.4.1. The vertices of a connected graph G can always be enumerated, say as v1,...,vn, so that Gi := G [ v1,...,vi ] is connected for every i. Proof . Pick any vertex as v1, and assume inductively that v1,...,vi have been chosen for some i < |G|. Now pick a vertex v ∈ G−Gi. As G is connected, it contains a v–v1 path P. Choose as vi+1 the last vertex of P in G − Gi; then vi+1 has a neighbour in Gi. The connectedness of every Gi follows by induction on i.
4 We shall often use terms defined for graphs also for walks, as long as their meaning is obvious.