Recall the definitions of graphs from Section 1.1.4. The degree of the vertex x was defined to be the number of edges that have x as an endpoint. We write degG(x) for the degree of x in gra…
Recall the definitions of graphs from Section 1.1.4. The degree of the vertex x was defined to be the number of edges that have x as an endpoint. We write degG(x) for the degree of x in graph G, or simply deg(x) if only one graph is being discussed. A graph is regular if all vertices have the same degree, and in particular a regular graph of degree 3 is called cubic. We denote the smallest of all degrees of vertices of G by δ(G), and the largest by ∆(G). The degree sequence of a graph consists of all the degrees of the vertices. For example, degree sequence (4, 2, 2, 1, 1, 0) corresponds to the graph