A $(3k+3)$-node graph with degrees $k+1,\dots,k+3$ has $k+3$ degree-$(k+1)$ nodes or $k+1$ degree-$(k+2)$ nodes or $k+2$ degree-$(k+3)$ nodes?

Question

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 degree $k+1$ or at least $k+1$ vertices of degree $k+2$ or at least $k+2$ vertices of degree $k+3$

I used the proof by cases.

In case 1: $k$ is odd I can show that $G$ has at least $k+1$ vertices of degree $k+2$. Otherwise it will contradict the theorem that say every graph have even number of odd vertices.

Same reason, in case 2: $k$ is odd I can show that at least $k+2$ vertices of degree $k+3$

I just can't figure out how to show $G$ has at least $k+3$ vertices of degree $k+1$

Answer 1

It seems like this final case has nothing to do with the actual value of each degree.

You're really after showing it has at least $k+3$ vertices of degree $k+1$ if it doesn't have at least $k+1$ vertices of degree $k+2$ and at least $k+2$ vertices of degree $k+3$.

Let $a,b,c$ denote the number of vertices with $k+1,k+2,k+3$ edges respectively. Assuming this is a simple graph (is it?), we have that $a+b+c=3k+3$. We are assuming $b<k+1$ and $c<k+2$. It follows that $a+k+1+k+2>3k+3$. So $a>k$, which means $a\geq k+1$.

Answer 2

Since $G$ has only vertices of degrees $k+1$, $k+2$ and $k+3$ you can split all of the vertices into 3 sets: $X$, $Y$ and $Z$ where $X$ is set of vertices with degree $k+1$, $Y$ with $k+2$ and $Z$ with $k+3$.

Now, since you already know the answers for cases:

$1)$ $|X|<k+3$ and $|Y|<k+1 \Rightarrow |Z|\geq k+2$

$2)$ $|X|<k+3$ and $|Z|<k+2 \Rightarrow |Y|\geq k+1$

we are interested in case 3, which is

$3)$ $|Y|<k+1$ and $|Z|<k+2 \Rightarrow |X|\geq k+3$

Proof for that case:

Suppose $k$ is odd. Then $|Y|$ can't equal $k$ since it is odd number and if it was equal $k$ it would contradict to the theorem that states that there is even number of vertices of odd degree so since $|Y|\leq k-1$ and $|Z| \leq k+1$, $|X| \geq k+3$.

Now suppose $k$ is even. Then $|Z|$ can't equal $k+1$ for the same reason as above (that means contradiction to the theorem that states that there is even number of vertices of odd degree), so $|Z|\leq k$ and then, since $|Y|\leq k$, $|X|$ must be equal or greater $k+3$.

For the cases

$4)$ $|X|<k+3$

$5)$ $|Y|<k+1$

$6)$ $|Z|<k+2$

the reasoning is very similar. Look at case $4)$.

If $|X|\leq k+2$ then we have at least $2k+1$ vertices for $Y$ and $Z$.

When $k$ is odd, $|Y|$ must be even and thus $|Y|\neq k$. If $|Y|<k$ then $|Z|\geq k+2$. If $|Y|>k$ then it is done, since $|Y|\geq k+1$.

When $k$ is even, $|Z|$ must be even. If $|Z|=k+2$ it is done. If not, then $|Z|\leq k$ or $|Z|\geq k+4$. In the second case it is done. If $|Z|\leq k$ then $|Y|\geq k+1$.

Answer 3

Let $a,b,c$ denote the number of vertices of degree $k+1,k+2,k+3$ respectively.
Then we have $a+b+c=3k+3$
If $a\geq k+3$ or $c\geq k+2$ then we are done.
Now if $a< k+3$ and $c< k+2$ then we have to show that $b\geq k+1$.

Thus we have $a\leq k+2$ and $c\leq k+1$. Now we consider two cases.

Case $1$: k is odd.
Putting the values of $a$ and $c$ in $a+b+c=3k+3$ we have $b\geq k$. Now if $b=k$, then the number of vertices containing odd($k+2$) degree is odd. So, $b\neq k$. Thus $b\geq k+1$.

Case $2$: k is even.
Now $a+c\leq 2k+3$. Now if $a+c=2k+3$, then the number of vertices containing odd($k+1$ and $k+3$) degree is odd($2k+3$). So, $a+c\neq 2k+3$. Therefore $a+c\leq 2k+2$. Putting this value in the equation $a+b+c=3k+3$ we have $b\geq k+1$. Hence proved.