1
$\begingroup$

Could someone verify this?

Pick a vertex $v$ of $G$. Pick distinct vertices $u_1, u_2, \ldots, u_d$ incident with $v$. Note that this can be done since $v$ has no loops and degree $\geq d$. For each $u_i$, pick distinct vertices $w_i^{(1)}, w_i^{(2)}, \ldots, w_i^{(d-1)}$ incident with $u_i$ other than $v$.

Then, $$w_i^{(k)} \neq w_j^{(l)}$$ To see this, note that $v, u_i, w_i^{(k)}, u_j, v$ would form a cycle of length $4$. Also, $$w_i^{(j)} \neq u_k$$ To see this, note that $v, u_k, u_i, v$ would form a cycle of length 3.

Also, $$v \neq w_i^{(j)}$$

Otherwise, $v, u_i, v$ would form a cycle of length $2$.

So, all of the edges $v, u_1, \ldots, u_d, w_1^{(1)}, \ldots, w_d^{(d-1)}$ are distinct. So, the graph contains at least $1+d+d(d-1) = 1+d^2$ vertices.$~~~~~~~~~$

$\endgroup$
  • 1
    $\begingroup$ You're right$~~$. $\endgroup$ – pointer Jun 15 '14 at 16:07
1
$\begingroup$

It looks great! Another approach is the following:

Let $V$ be the set containing the vertex $u$ and it's neighbors. We see that $|V|\geq d+1$ since every vertex in $G$ has degree at least $d$. None of $u$'s neighbors are adjacent since $G$ has girth $5$. Consider $V-u$, every vertex in $V-u$ has degree at least $d-1$ and $|V-u|=d$. So $|\bar{V}|\geq d(d-1)=d^2-d$. Thus $G$ has at least $(d+1)+(d^2-d)=d^2+1$ vertices.

$\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.