51.2 The degree of a vertex1.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(u).1 More generallyN(u)for U , the neighbours in VU of vertices in U are called neighboursof U; their set is denoted by N(U).The degree (or walency) de(u) = d(u) of a vertex y is the numberdegree d(u)[E(u)/ of edges at v; by our definition of a graph,? this is equal to thenumber of neighbours of v. A vertex of degree O is isolated. The number isolated(G) := min [ d(u) I u e V) is the minimum degree of G, the number5(G)A(G) := max (d(o) I 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. Aregular3-regular graph is called cubic.cubicThe number1d(u)d(G) :=VIEVa(G)areis 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. Sometimes it willbe convenient to express this ratio directly, as e(G) := [E|/lV)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:oncefrom each of its ends. Thus[E=d() = d(G):IVI,VEVand thereforee(G) = d(G).Proposition 1.2.1. The number of vertices of odd degree in a graph is[10.3.3]always evenProof. A graph on V has Euevd(u) edges, so Ed(o) is an even口number.Hereaselsewhre, wedohindxrringothunderlnggraphireferenceisclear2but 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) ofavertex 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.3 ] always even. Proof . A graph on V has 1 2 v∈V d(v) edges, so d(v) is an even number.
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