Minimum degree

Definition

Let $G$ be a finite graph with a nonempty vertex set $V$. The minimum degree of $G$ is $$\delta(G) = \min_{v \in V} \deg(v),$$ the smallest degree of a vertex of $G$.

Remarks

The maximum degree $\Delta(G)$ is the largest degree. Always $\delta(G) \le \Delta(G)$. Each cycle graph has $\delta = 2$, and each tree with at least two vertices has $\delta = 1$. A condition on $\delta(G)$ gives a Hamiltonian cycle in Dirac's theorem.

Explanations

L1 human

The minimum degree is the smallest number of edges at any vertex. If $\delta(G) = 3$, then each vertex has at least three neighbours.