Prove that for any $n \ge 3$, with $n \in \mathbb{N}$, there is a $G$ graph with $n$ vertices, which doesn't contain three vertices with same degree.
I started with induction by $n$.
For $n=3$, we can take vertices $\{a,b,c\}$, and edges $e_1 = ab, e_2 = ac$
Now assuming that it is valid for $n$, we must show it for $n+1$.
I tried to seperate two cases.
-
Case 1:
if there is a vertex with some degree, then there is also another one (graph contains two vertices with same degree), and adding a new vertex, will just add biggest degree + 1 edges
-
Case 2:
When there is at least one vertex, with unique degree, and new vertex will be connected with edges, as much it has vertex with unique degree.
But it seems wrong. Any tips or helps are welcome.
Best Answer
We can consider a special construction for this question. I will first explain how can we construct such a graph in general case (for $n$) and then give some examples to make it more concrete.
Suppose we have $n$ vertices. Then put them in line and name them as $x_1, x_2, ..., x_n$. After that;
Connect $x_1$ to every vertex up to $x_n$ ($x_n$ included). So we have $d(x_1) = n-1$.
Connect $x_2$ to every other vertex up to $x_{n-1}$ (included again). So we have $d(x_2) = n-2$
Continuing like this, since $x_n$ will have only one connection throughout this process, we have $d(x_n) = 1$ and similarly $d(x_{n-1}) = 2$ and so on. Now we need to find when this process will stop.
Notice that while we are incrementing the index of the vertex from $x_1$ side, we also decrement the index of the vertex from $x_n$ side. So we can say that process should stop after $\lfloor n/2 \rfloor$ steps. Also notice that after $i^{th}$ step, we certainly got two vertices with degrees $n-i$ and $i$, where $i \le \lfloor n/2 \rfloor$.
Now, when $n$ is even, after $n/2$ steps, we will have two vertices with same degree, which is $n-n/2 = n/2$. All of the other vertices will have distinct degrees $n/2-1$, $n/2+1$, $n/2-2$, $n/2+2$, ..., $n-1$, $1$.
When $n$ is odd, first $(n-1)/2$ and last $(n-1)/2$ vertices have distinct degrees, similarly, so we are left with one vertex whose degree is not known. However even if it is as same as one of the other degrees, we can have at max two vertices with the same degree so we are done.
Here is an example construction for $n = 7$. For understanding how the construction is done, could you further construct the graphs for $n = 8$ and $n = 9$?
HINT: You can add new vertices to the end of the construction that I have made for you. Then you will only need to make some additional connections without changing the current ones in order to construct a graph with only two vertices with the same degree.