Prove the existence of graph, which doesn't contain three vertices with same degree.

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.

Let $\Psi(n)$ be the statement

There exists a simple undirected graph with $n$ vertices such that for every $k$, the graph
has at most two vertices of degree $k$.

Let $\Phi(n,d)$ be the statement

There exists a simple undirected graph $G=G(n,d)$ with $n$ vertices with a special vertex $v$ and the following properties:

• At most four vertices have degree $d$
• For $k\ne d$, at most two vertices have degree $k$
• $\deg v=d$
• If $u$ is a neighbour of $v$, then $\deg u\le d$
• At most one neighbour of $v$ has degree $d$.

Note that $\Phi(n,d)$ implies $\Psi(n)$ if $d\ge n$ because degrees cannot exceed $n-1$.

Lemma 1. If $\Phi(n,d)$ then $\Phi(n,d+1)\lor\Psi(n)$.

Proof. Assume $\Phi(n,d)$ and $\neg \Psi(n)$. Consider $G(n,d)$ with special vertex $v$. As $\Psi(n)$ is false, $G(n,d)$ must have at least three vertices of degree $d$. One of these is $v$, at most one other is a neighbour of $v$. hence we can find $w$ with $\deg w=d$ that is neither $v$ nor a neighbour of $v$. Let $G(n,d+1)$ be $G(n,d)$ with edge $vw$ added.

• The only possible vertices of degree $d+1$ are $v,w$, and up to two vertices of degree $d+1$ in $G(n,d)$
• As $v,w$ no longer have degree $d$, at most two vertices have degree $d$. For $k\ne d,d+1$, we still have at most two vertices of degree $k$.
• $\deg v=d+1$ due to the additional edge
• $\deg u\le d<d+1$ for all "old" neighbours of $v$, and $\deg w=d$ for the new neighbour

$\square$

Lemma 2. If $\Psi(n)$ then $\Phi(n+1,0)$.

Proof. Given a graph as described by $\Psi(n)$, add a new vertex $v$ without edges and call the resulting graph $G(n,0)$. The five bullet points are readily verified: At most three vertices have degree $0$; for $k>0$, at most two vertices have degree $k$; $\deg v=0$; claims about $v$'s neighbours are vacuously true. $\square$

Using lemma 1 and induction on $d$, we see that $$ \Phi(n,0)\implies \Psi(n)\qquad\text{for all }n.$$ Together with lemma 2, this gives us $$ \Psi(n)\implies \Psi(n+1)\qquad\text{for all }n$$ so that (starting form the trivially true $\Psi(1)$) we get $$ \Psi(n)\qquad\text{for all }n$$ by induction.

Unless given the additional property that the graphs are simple, the proof is trivial.

Label all vertices with a unique natural number. Create as many loops from each vertex to itself, as its label number.

The degree is then double the label number, and these are unique, so the degrees are unique, so there are never two or more vertices with the same degree.