The maximum degree of a graph , denoted by , is the maximum of its vertices’ degrees.