Prove that a simple graph with n >_ 2 vertices must have atleast two vertices with the same degree. There was a hint given in the book saying that the key to this is the graph can not have both a vertex of 0 degree and a vertex of n-1 degree
Thanks
I don't understand what you mean by a vertex having a 'degree'.
It means that it is attached to that many other vertexes, say if a vertex is attached to two other vertex by lines then it has degree 2
Matt, I am afraid you have me stumped on that one, I have never encountered that kind of geometry before.
Perhaps if you repost your question some of the other math tutors could help you.
To prove that a simple graph with n ≥ 2 vertices must have at least two vertices with the same degree, we can use the Pigeonhole Principle.
The Pigeonhole Principle states: "If you have more pigeons than pigeonholes, then at least one of the pigeonholes must contain more than one pigeon."
Consider the degrees of the vertices in the graph. The degree of a vertex is defined as the number of edges incident to it.
Now, let's assume that in our simple graph with n vertices, no two vertices have the same degree.
Let's consider the range of possible degrees a vertex can have in this graph. The minimum degree is 0, which corresponds to a vertex with no edges incident to it. The maximum degree is n-1, where a vertex is connected to all other vertices in the graph.
By the hint given in the book, we know that the graph cannot have both a vertex of 0 degree and a vertex of n-1 degree. This implies that the range of degrees in the graph is at most n-2.
Now, since we have n vertices and a range of at most n-2 degrees, we can apply the Pigeonhole Principle. There are more vertices (pigeons) than the possible degrees (pigeonholes).
According to the Pigeonhole Principle, at least two vertices must have the same degree. This completes the proof.