Define a finite graph (V,E) where V is a finite, non-empty set and
E is a subset of { {a,b} | a,b in V and a ≠ b }.

If c in V, we define

   E(c) = { {a,c} in E | a in V }

   V(c) = { a in V | {a,c} in E }

   d(c) = |E(c)| = |V(c)|

Prove for any finite graph (V,E), with |V| > 1, that
there exists a,b in V such that a ≠ b and d(a) = d(b).

Note:

   V is the set of vertices of the graph.

   E is the set of edges of the graph.

   E(c) is the set of edges incident to vertex c.

   V(c) is the set of vertices adjacent to vertex c.

   d(c) is the degree of vertex c.

Consider the number of different possible values for d(c) given |V| = some number N. d(c) must be a whole number. It can be as small as zero (for an unconnected vertex) or as large as N-1. (A vertex can't be connected to all N vertices because it can't be connected to itself by the definition of E) That's a total of N possible values.

On the surface, N possible values and N vertices to spread them among sounds plausible, but there's a fly in the ointment. One of those values for d(c) is N-1, which requires the vertex to be connected to ALL of the other vertices. Another of those values for d(c) is 0, which requires that NOTHING be connected to that vertex. Clearly, then, a graph can't have both a vertex with d(c) =0 and a vertex with d(c) = N-1, so there are at most N-1 (instead of N) possible values of d(c) that can fit in a graph.

Since there are N vertices and only N-1 possible values to assign to them, the pigeonhole principle demands that at least one pair have the same d(c) value. 

Posted by Paul on 2008-08-22 22:07:58