| Interesting Math Problem | Math Problems Home | Home | Send Feedback |
|
The following proof was sent to me by Andrew Hughes: If all the degrees of a graph of n vertices are different, they must be exactly, {0, 1, 2, ...., n-1}. But it is impossible to have a vertex of degree 0 (connected to no other vertex) and one of degree n-1, (connected to every other vertex) simultaneously. Thus there is no such graph. |
You can prove it by induction. A graph with 2 vertices has either 0 or 1 edges, and in either case, the two nodes have the same degree. Assume the theorem holds for k vertices and there are two (or more) of same degree. The existing k vertices have at most (k-1) different degrees 0,1,2, ...., k-1 (with at least one missing, and at least one pair). [ by induction hypothesis ] Add another node and, one by one, its edges. If it stays degree 0, whatever existing pairs there were remain. When the first new edge is added, the new node has degree 1, and we have one of the following possibilities: 1) connected to a node with a unique degree: An existing pair of vertices with equal degrees remains intact. 2) connected to a member of a pair of same degree. 2a) if there is another pair, that pair remains. 2b) if this was the only pair, let it be degree d and before we added this edge, the list of degrees was 0, 1, 2, ..., d-1, d , d, d+1, d+2, .... k-1 with one element missing. 2b.i) d+1 was missing: Now we have a pair of 1's. 2b.ii) Some other degree was missing: Now we have a pair of d+1's. This is the situation for each new edge added, but a different constant instead of 1 as the degree of the new node increases. Therefore, there is always a pair. |
