Who doesn't love proofs?!
So, we have a graph G with e edges and v vertices. Define M as the maximum degree of all of the vertices of G, and m as the minimum degree of all vertices of G. We want to show that (a.) 2e/v ≥ m and (b.) 2e/v ≤ M.
Start by noting the handshaking theorem: The sum of the degrees of all of the vertices in the graph -- call this number D -- is equal to twice the number of edges. In other words, D = 2e. Also, consider the degrees of each vertex in G; we will call them d_1, d_2, ..., d_v. By definition, D = d_1 + d_2 + ... + d_v. (*)
(It may be helpful for our intuition to note at this point that the average degree of a vertex is D/v = 2e/v. It should be apparent, then, that we can't have all vertices with degrees higher than this (m > 2e/v) or all vertices with degrees lower than this (M < 2e/v).)
m = min(d_1, d_2, ..., d_v), and M = max(d_1, d_2, ..., d_v), by definition.
a. First, let's consider m > 2e/v and prove that this cannot happen by contradiction. d_1 + d_2 + ... + d_v > v * min(d_1, d_2, ..., d_v) = v * m > 2e = D. --><-- (*). Thus, m ≤ 2e/v.
b. Now, similar to a, let's consider M < 2e/v and prove that this cannot happen by contradiction. d_1 + d_2 + ... + d_v < v * max(d_1, d_2, ..., d_v) = v * M < 2e = D. --><-- (*). Thus, M ≥ 2e/v.
--Thomas34 23:57, 5 November 2008 (UTC)
