A graph G has order n=3k+3 for some positive integer k. Every vertex of G has de
ID: 2987830 • Letter: A
Question
A graph G has order n=3k+3 for some positive integer k. Every vertex of G has degree k+1, k+2, or k+3. Prove that G has at least k+3 vertices of k+1, or at least k+1 vertices of degree k+2, or at least k+2 vertices of degree k+3.
I am assuming you have to use the fact that the total degree must be less than or equal to the floor function of (n^2)/4 (and the fact that size is related to degree), but I am not sure how to exactly. Also, I think it must be a case by case proof. Test today so help appreciated :]
Explanation / Answer
Let n_j denote the number of vertices in G of degree k+j for j = 1, 2, 3. By hypothesis n_1 + n_2 + n_3 = 3k+3.
If n_2 >= k + 1 or n_3 >= k + 2 we are done, so we may assume that n_2 < k + 1 and n_3 < k + 2. Then we have n_2 <= k and n_3 <= k + 1, and hence
3k + 3 = n_1 + n_2 + n_3 <= n_1 + k + (k + 1)
so that 3k + 3 <= n_1 + 2k + 1 and hence k + 2 <= n_1. We only need to show that n_1 = k + 2 cannot happen.
If n_1 = k + 2, we must have n_2 + n_3 = (3k + 3) - (k + 2) = 2k + 1 and since n_2 <= k we deduce from 2k + 1 = n_2 + n_3 <= k + n_3 that k + 1 <= n_3 and hence (as we knew n_3 <= k + 1 already) that n_3 = k + 1, and therefore n_2 = (2k + 1) - n_3 = k. So we have in this case that n_1 = k + 2 and n_2 = k and n_3 = k + 1.
It is a general fact that in any graph, the number of vertices of odd degree is even. To see why note that
[the sum of all the degrees of the vertices in the graph] = 2 [the number of edges in the graph]
is certainly even, and the left hand side is the sum
[the sum of the degrees of the vertices of even degree] + [the sum of the degrees of the vertices of odd degree].
As first sum in brackets here is a sum of even numbers, and hence even, we deduce that the second sum in brackets is also even. But it is a sum of odd numbers, and a sum of an odd number of odd numbers is odd. So there must be an even number of vertices of odd degree.
With that fact in mind, consider the two possibilities for k.
Case 1, k is even: In this case the vertices of odd degree in the graph are those with degree k + 1 and k + 3. The total number of them is n_1 + n_3 = (k + 2) + (k + 1) = 2k + 3--- but this is odd, a contradiction.
Case 2, k is odd: In this case the vertices of odd degree in the graph are those with degree k + 2. The total number of them is n_2 = k, which is again odd (because k is), a contradiction.
So in fact it is not possible for n_1 to be equal to k + 2 and we deduce from n_1 >= k + 2 that n_1 >= k + 3, as desired.