The minimum vertex degree, sometimes simply called the minimum degree, of a graph is the smallest vertex degree of , denoted .
It is a well known consequence of the Euler theorem that a planar graph has (Fabrici and Madaras 2007). Fabrici and Madaras (2007) showed that a 1-planar graph has .