(Brian Thomas Rhea HW10) |
(...and my sig :p -Brian) |
||
| Line 12: | Line 12: | ||
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. | 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. | ||
| + | |||
| + | --[[User:Thomas34|Thomas34]] 23:57, 5 November 2008 (UTC) | ||
Revision as of 18:57, 5 November 2008
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 nodes with degrees higher than this (m > 2e/v) or all nodes 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)
