Mindestgrad

Mindestgrad, in graph theory, denotes the minimum degree of a graph G. The degree deg(v) of a vertex v is the number of edges incident with v, and der Mindestgrad δ(G) is defined as the smallest degree among all vertices: δ(G) = min{deg(v) : v ∈ V(G)}. For simple graphs, δ(G) ranges from 0 to n−1, where n is the number of vertices. Examples include δ(Cn) = 2 for any cycle, δ(Kn) = n−1 for a complete graph, and δ(G) = 0 for an edgeless graph on n vertices.

Consequences and uses: If δ(G) ≥ k, every vertex has at least k neighbors. This does not guarantee connectivity (a graph can be disconnected even with δ(G) ≥ 1, for instance two disjoint cycles), but higher minimum degree yields stronger properties. Dirac’s theorem states that if n ≥ 3 and δ(G) ≥ n/2, then G contains a Hamiltonian cycle. More generally, there is a relationship between minimum degree and connectivity: every k-connected graph satisfies δ(G) ≥ k, and the standard inequalities are κ(G) ≤ λ(G) ≤ δ(G), where κ is vertex-connectivity and λ is edge-connectivity.

Computation and variants: To determine δ(G), compute deg(v) for all vertices and take the minimum. In directed graphs one often speaks of minimum in-degree δ−(G) and minimum out-degree δ+(G). The concept is widely used in studies of graph expansion, resilience, and threshold phenomena in random graphs, where minimum degree conditions frequently serve as simplifying criteria for guaranteeing certain structures.