Prove that, for all n, there is an n-vertex graph containing a vertex of every degree between
1 and n − 1. One of these degrees will occur twice.
To prove that, for all n, there is an n-vertex graph containing a vertex of every degree between 1 and n-1, we can use the concept of a complete graph.
A complete graph is a simple undirected graph where every pair of distinct vertices is connected by a unique edge. The degree of each vertex in a complete graph is equal to n-1.
Now, if we remove a single edge from a complete graph, we will have a graph with n vertices and every degree between 1 and n-1, except for the degree of 0.
To show that one of these degrees will occur twice, we can use the Pigeonhole Principle, which states that if n+1 objects are placed into n boxes, then at least one box must contain two or more objects.
In this case, the "objects" refer to the degrees of the vertices, and the "boxes" refer to the possible degrees between 1 and n-1.
Since there are n vertices and n-1 possible degrees, by placing the degrees into boxes, at least one box must contain two or more degrees. This means that there will be at least two vertices in the graph with the same degree.
Therefore, we have proven that for all n, there is an n-vertex graph containing a vertex of every degree between 1 and n-1, and one of these degrees will occur twice.