minimum degree

• unknown source
  • minimum degree upper bounds edge connectivity by a linear function – Removing edges incident to the minimum degree vertex disconnects the graph.
  • minimum degree upper bounds domatic number by a linear function – The vertex of minimum degree needs to be dominated in each of the sets. As the sets cannot overlap there can be at most $k+1$ of them.
  • minimum degree – minimum degree of graph’s vertices
• assumed
  • average degree upper bounds minimum degree by a linear function – By definition
• Bodlaender1998
  • page 38 : treewidth upper bounds minimum degree by a linear function – Lemma 90 (Scheffler [94]). Every graph of treewidth at most $k$ contains a vertex of degree at most $k$.