The Maximum and Minimum Degrees of a Graph

The Maximum and Minimum Degrees of a Graph

Definition: For a graph $G = (V(G), E(G))$, the Maximum Degree of $G$ denoted by $\Delta (G)$, is the degree of the vertex with the greatest number of edges incident to it. The Minimum Degree of $G$ denoted by $\delta (G)$, is the degree of the vertex with the least number of edges incident to it.

For example, consider the following graph:

Screen%20Shot%202014-02-18%20at%2012.54.19%20PM.png

The degree sequence of this graph is $(1, 2, 3, 3, 4, 4, 4, 4, 4)$. Hence $\Delta(G) = 4$, and $\delta (G) = 1$.

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License