Math 2.0

Combinatorics Definition

Minimum degree

Builds on Degree of a vertex

Definition

Let GG be a finite graph with a nonempty vertex set VV. The minimum degree of GG is δ(G)=min⁡v∈Vdeg⁡(v),\delta(G) = \min_{v \in V} \deg(v), the smallest degree of a vertex of GG.

Remarks

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

Reading path

To understand this page from the ground up, read these 4 pages in order. The foundations come first.

Show the path as a graph
Graph, definition, no evidence levelGraphdefinitionNeighbourhood, definition, no evidence levelNeighbourhooddefinitionDegree of a vertex, definition, no evidence levelDegree of a vertexdefinitionMinimum degree, definition, no evidence levelMinimum degreedefinition
Each page uses the pages above it. The colour of the bar on a box shows how strong the evidence is, and the box also gives it as text. The list has the same pages.
  • no evidence level
  1. Graph definition
  2. Neighbourhood definition
  3. Degree of a vertex definition
  4. Minimum degree definition

Where this leads

1 page builds on this one.

Further reading

  1. Web https://en.wikipedia.org/wiki/Degree_(graph_theory), Special values
About this page
Tag0TKZCSGCCA
URIm2://0TKZCSGCCA
Kinddefinition
WritingW0 stub
MSC05C07
DefinesMinimum degree
UsesDegree of a vertex

Markdown · JSON · Edit on GitHub

What this page needs for W1

  • an inventory row: the row of the inventory that the node accounts for (0 of 1)

The writing levels say how complete the text of a page is. They do not measure its truth.

What links here

Used by