1.2. The degree of a vertex51.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().' More generallyN(u)for U V, the neighbours in VU of vertices in U are called neighboursof U; their set is denoted by N(U),egree (or valency) dc(u) =- d(u) of a vertex u is the numberdegree d(u)[E(u)[ of edgeesatw:byourdefiron of a graph,? this is equal to thember ofneighboursofu.Avertex ofdegreeOis isolated.Thenumberisolateds(G) := min ( d(v) [ w e V) is the minimum degree of G, the number8(G)A(G) := max ( d(u) I u 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. Aregularcubic3-regular graph is called cubic.The numberd(G)=mEd(u)Vd(G)is 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. Somesitwillbe convenient to express this ratio directly, as e(G) := [El/IV].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: once from each of its ends. Thus[E] = d(0) = d(G) [V],and therefore(G) = d(G)Proposition 1.2.1. The num[10.3.1]of vertices of odd degree inagraph isalwavseven口Proof. As [E] - Zvev d(u) is an integer, Zvev d(u) is even.LHerelsewhere, we drop the index referring to the underlying graph if threference is clear.2 but not for multigraphs: see Section 1.101.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) of a vertex 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.1] always even. Proof. As |E| = 1 2  v∈V d(v) is an integer,  v∈V d(v) is even. 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