Lower bound on number of vertices of some specific graph

71 Views Asked by At

Let $\Gamma$ be a graph such that for any vertex $v$ we have that $\deg v \geq 50$ and there is two vertices $a, b$ such that $d(a,b) = 8$. Than number of vertices $|V| \geq 200$.

Since balls $B_a(1), B_b(1)$ doesn't intertersect we have at least $102$ vertices. And i want bound say $|B_a(2)-B_a(1)|$. We know that there is at least one vertex $a_2\in B_a(2)-B_a(1)$ and i stuck with futher bounds...

1

There are 1 best solutions below

0
On

I don't think this is true.

Consider the graph $\Gamma$ with subgraphs $G_i$, $i = 0, \dots, 8$, such that $|G_i|$ is as follows:

\begin{array}{|c|c|c|c|c|c|c|c|c|} \hline 0& 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 \\ \hline 1& 50 & 1 & 1 & 50 & 1 & 1 & 50 &1\\ \hline \end{array}

Further, suppose there is an edge between $g \in G_i$ and $h \in G_j$ whenever $|i - j| \leq 1$. (So e.g. the single vertex in $G_2$ is connected to all 50 vertices in $G_1$ and the single vertex in $G_3$.)

Then $\deg v \geq 50$ for all $v \in G$. Let $a$ be the unique element of $G_0$ and $b$ be the unique element of $G_8$. Then if $v \in G_i$ then $d(v, a) = i$, and in particular $d(a, b) = 8$.

And this $\Gamma$ has 156 elements, which is less than 200.