degeneracy (1162B)
1 # Degeneracy 2 3 https://en.wikipedia.org/wiki/Degeneracy_(graph_theory) 4 5 An [undirected_graph] is k-degenerate if every [subgraph] has at least one [vertex] of [degree] at most k 6 - it does not make a difference whether we define this via [subgraphs] or via [induced_subgraphs] 7 - cf https://en.wikipedia.org/wiki/Degeneracy_(graph_theory)#Examples 8 9 Special case: [2_degenerate_graphs] 10 11 Some [enumeration] and [counting] problems on graphs have been studied based on degeneracy and arboricity, see [danisch2018listing] for example 12 13 Generalization to [relational_databases]: [partition_constraints] introduced in [deeds2025partition] 14 15 The [arboricity] is no greater than the degeneracy, and the degeneracy is at most twice the [arboricity]. 16 - source https://en.wikipedia.org/wiki/Degeneracy_(graph_theory)#Relation_to_other_graph_parameters 17 18 The degeneracy of an [undirected_graph] is equal to the [maximum_degree] if and only if one of the [connected_components] is a [regular_graph] https://en.wikipedia.org/wiki/Degeneracy_(graph_theory)#Examples 19 20 A [k_vertex_connected] graph has degeneracy at most k 21 22 Up: [width_measure] 23 24 See also: [arboricity], [thickness]