9
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ This is indeed wrong. You can't just say, "I'll add so many edges." You have to say which vertices the edges will join. Note also, that as you add edges, you change the degree of some vertices, and may impair the condition that no three have the same degree. $\endgroup$ – saulspatz Apr 2 '18 at 20:48
  • $\begingroup$ @saulspatz Yes you are right, In some cases it may work, but not always $\endgroup$ – Spike Bughdaryan Apr 2 '18 at 20:53
  • $\begingroup$ I don't think you need $n\ge3.$ $\endgroup$ – bof Apr 2 '18 at 21:04
  • $\begingroup$ How about $V=\{1,2,\dots,n\}$ and $E=\{xy:x\lt y, x\text{ even, }y\text{ odd}\}$? $\endgroup$ – bof Apr 2 '18 at 21:05
  • $\begingroup$ @bof Seems correct, but I need formal proof, it is hard to prove in that way by induction $\endgroup$ – Spike Bughdaryan Apr 2 '18 at 21:15
4
$\begingroup$

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$?

graph

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.

$\endgroup$
  • $\begingroup$ Great. That was very beautiful $\endgroup$ – Spike Bughdaryan Apr 2 '18 at 21:39
  • $\begingroup$ Thank you, the way you asked the question was also great :) $\endgroup$ – ArsenBerk Apr 2 '18 at 22:03
4
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.