TOPICS
Search

Minimum Vertex Degree


The minimum vertex degree, sometimes simply called the minimum degree, of a graph G is the smallest vertex degree of G, denoted delta.

It is a well known consequence of the Euler theorem that a planar graph has delta<=5 (Fabrici and Madaras 2007). Fabrici and Madaras (2007) showed that a 1-planar graph has delta<=7.


See also

Maximum Vertex Degree, Vertex Degree

Explore with Wolfram|Alpha

References

Fabrici, I. and Madaras, T. "the Structure of 1-Planar Graphs." Disc. Math. 307, 854-865, 2007.Skiena, S. Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, p. 157, 1990.

Cite this as:

Weisstein, Eric W. "Minimum Vertex Degree." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/MinimumVertexDegree.html