Math 2.0

definition

Maximum degree

Definition

Let GG be a finite graph with a nonempty vertex set VV. The maximum degree of GG is Δ(G)=max⁡v∈Vdeg⁡(v),\Delta(G) = \max_{v \in V} \deg(v), the largest degree of a vertex of GG.

Remarks

The complete graph KnK_n has Δ=n−1\Delta = n - 1. A greedy colouring uses at most Δ(G)+1\Delta(G) + 1 colours. Brooks' theorem improves this to Δ(G)\Delta(G) in most cases.

Explanations

L1 human

The maximum degree is the largest number of edges at any vertex. In a star with one centre and 55 leaves, the maximum degree is 55.

What this node 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 node is. They do not measure its truth.

What this needs

To read this node, read these 4 nodes in this order. The foundations come first, and the list ends with this node.

Graph, definition, no evidence levelGraphdefinitionNeighbourhood, definition, no evidence levelNeighbourhooddefinitionDegree of a vertex, definition, no evidence levelDegree of a vertexdefinitionMaximum degree, definition, no evidence levelMaximum degreedefinition
Each node uses the nodes above it. The colour of the bar on a box shows the evidence level, and the box also gives it as text. The list below has the same nodes.
  • no evidence level
  1. Graph definition
  2. Neighbourhood definition
  3. Degree of a vertex definition
  4. Maximum degree definition

What depends on this

1 node uses this node, directly or through other nodes.

Sources

  1. Web https://en.wikipedia.org/wiki/Degree_(graph_theory), Special values

What links here

Used by