I am reading a proof for a problem that uses Euler's formula; the sum of the degree of vertices in a graph is equal to twice the amount of edges.
The proof goes on and elaborates on this formula stating that the previous sum is less than or equal to the sum of the maximum degree of vertices. I cannot understand how there is a sum of maximum degree vertices. Shouldn't there only be one?
Can someone please elaborate on how this was deduced and how that is equal to the number of vertices times the maximum degree of a vertex v?
$$\sum_{v \in V} deg(V) \le \sum_{v \in V} (max\ deg(V)) = \vert V\vert\cdot max\ deg(V)$$
Best Answer
Let $\Delta(G)$ be the maximum degree of the graph $G$ - that is, the largest degree of any vertex. Then we have $$\deg(v) \le \Delta(G)$$ for all $v \in V$, and therefore we may take the sum of both sides of the inequality above, for each $v \in V$, to get the inequality $$ \sum_{v \in V} \deg(v) \le \sum_{v \in V} \Delta(G). $$ The second sum here is a sum of constants: for every $v \in V$, we are taking the same value $\Delta(G)$, not depending on $v$. This is because $\Delta(G)$ is an upper bound on each term of the first sum. We are not taking a sum over maximum degree vertices; the sum still ranges over all vertices $v$, it is just ignoring the actual value of $\deg(v)$ and instead using the upper bound $\Delta(v)$.
Because the second sum is a sum of constants, its value is just the number of terms, multiplied by the value of a term. So we get $$ \sum_{v \in V} \deg(v) \le \sum_{v \in V} \Delta(G) = \Delta(G) \cdot |V|. $$
What may be confusing is that in the notation $$ \sum_{v \in V} (\max_{v \in V}\deg v) $$ the variable $v$ is being used twice: first, as the variable the sum ranges over, and second, as the variable the max is being taken over. This is just bad notation. Better would be to write $$ \sum_{v \in V} (\max_{w \in V}\deg w) $$ in which case it's clear that the terms of the sum don't depend on $v$, or to define $\Delta(G) = \max_{w\in V}\deg w$ separately, as I have done above.