Maximum degree of triangle.

Question

Let $\Delta$ denote the maximum degree of a graph, $$ \Delta = \max_u n_u. $$

In layman terms, what is this definition saying and what does it mean by maximum and minimum degree?

(This is part of a programming question involving connected graphs)

Answer 1

Without more context it's hard to guess exactly, but I think if you have a graph $G$ with vertices $V = \{v_1, \ldots, v_n\}$, we can define the degree of each vertex as the number of edges in $G$ adjacent to it.

Then, maximum and minimum degree are the max and min of the set of degrees for every vertex.

UPDATE - EXAMPLES

• In a cycle on $n$ vertices, both minimal and maximal degree are $2$.
• In a complete graph on $n$ vertices, both minimal and maximal degree are $n-1$.
• In a graph which looks like a square (on $4$ vertices) with one added diagonal, the minimal degree is $2$ (in any one of 2 vertices without the diagonal) and the maximal degree is $3$ (in one of vertices touching the extra diagonal).